Relations and equivalences between circuit lower bounds and Karp-Lipton theorems

Relations and equivalences between circuit lower bounds and Karp-Lipton theorems

© Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams; licensed under Creative Commons License CC-BY 34th Computational Complexity Conference (CCC 2019). A frontier open problem in circuit complexity is to prove PNP 6⊂ SIZE[nk] for all k; this is a necessary intermediate step towards NP...

Full description

Bibliographic Details
Main Authors: Williams, Richard Ryan, Murray, Cody, Chen, Lijie, McKay, Dylan M.
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: 2021
Online Access:https://hdl.handle.net/1721.1/137582

Internet

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

Similar Items