Strong co-nondeterministic lower bounds for NP cannot be proved feasibly

DOI10.1145/3406325.3451117OpenAlexW3152990700MaRDI QIDQ6086996

Ján Pich, Rahul Santhanam

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:4bb0ed7a-1983-4d95-8296-ab973094292e

zbMATH Keywords

bounded arithmeticcircuit complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Unprovability of strong complexity lower bounds in bounded arithmetic ⋮ Indistinguishability obfuscation, range avoidance, and bounded arithmetic

This page was built for publication: Strong co-nondeterministic lower bounds for NP cannot be proved feasibly