Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma

Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma

© 2020 Society for Industrial and Applied Mathematics. We prove that if every problem in N P has nk-size circuits for a fixed constant k, then for every N P -verifier and every yes-instance x of length n for that verifier, the verifier's search space has an nO(k3)-size witness circuit: A witnes...

Full description

Bibliographic Details
Main Authors: Murray, Cody D, Williams, R Ryan
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:English
Published: Society for Industrial & Applied Mathematics (SIAM) 2021
Online Access:https://hdl.handle.net/1721.1/134017

Internet

https://hdl.handle.net/1721.1/134017

Similar Items