Consequences of the provability of NP ⊆ P/poly
From MaRDI portal
Publication:5444705
DOI10.2178/jsl/1203350791zbMath1133.03035OpenAlexW2087012565MaRDI QIDQ5444705
Publication date: 25 February 2008
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://projecteuclid.org/euclid.jsl/1203350791
bounded arithmeticnonuniform complexity classescollapse of the polynomial hierarchyproof systems with advice
First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items
INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH ⋮ On an optimal randomized acceptor for graph nonisomorphism ⋮ Circuit lower bounds in bounded arithmetics ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Proof systems that take advice ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ Nondeterministic Instance Complexity and Proof Systems with Advice ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ On the amount of nonconstructivity in learning formal languages from text ⋮ Does Advice Help to Prove Propositional Tautologies? ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ Induction rules in bounded arithmetic ⋮ Do there exist complete sets for promise classes? ⋮ Unprovability of circuit upper bounds in Cook's theory PV
Cites Work
- Unnamed Item
- Structure and definability in general bounded arithmetic theories
- On truth-table reducibility to SAT
- Bounded arithmetic and the polynomial hierarchy
- Bounded queries to SAT and the Boolean hierarchy
- Relating the bounded arithmetic and polynomial time hierarchies
- The strength of replacement in weak arithmetic
