Conference item
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
- Abstract:
- We show unconditionally that Cook’s theory PV formalizing poly-time reasoning cannot prove, for any non-deterministic poly-time machine M defining a language L(M), that L(M) is inapproximable by co-nondeterministic circuits of sub-exponential size. In fact, our unprovability result holds also for a theory which supports a fragment of Jeřábek’s theory of approximate counting APC1. We also show similar unconditional unprovability results for the conjecture of Rudich about the existence of super-bits.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 422.8KB, Terms of use)
-
- Publisher copy:
- 10.1145/3406325.3451117
Authors
- Publisher:
- Association for Computing Machinery
- Host title:
- STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
- Pages:
- 223-233
- Publication date:
- 2021-06-15
- Acceptance date:
- 2021-02-06
- Event title:
- STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing
- Event location:
- Online
- Event website:
- http://acm-stoc.org/stoc2021/
- Event start date:
- 2021-06-21
- Event end date:
- 2021-06-25
- DOI:
- ISBN:
- 978-1-4503-8053-9
- Language:
-
English
- Keywords:
- Pubs id:
-
1161005
- Local pid:
-
pubs:1161005
- Deposit date:
-
2021-02-10
- ARK identifier:
Terms of use
- Copyright holder:
- Pich and Santhanam.
- Copyright date:
- 2021
- Rights statement:
- © 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.
- Notes:
- This is the accepted manuscript version of the conference paper. The final published version is available from ACM at https://doi.org/10.1145/3406325.3451117
If you are the owner of this record, you can report an update to it here: Report update to this record