Consequences of the provability of NP ⊆ P/poly

DOI10.2178/jsl/1203350791zbMath1133.03035MaRDI QIDQ5444705

Jan Krajíček, Stephen A. Cook

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

zbMATH Keywords

bounded arithmetic; nonuniform complexity classes; collapse of the polynomial hierarchy; proof systems with advice

Mathematics Subject Classification ID

03F30: First-order arithmetic and fragments

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03F20: Complexity of proofs

Related Items

On an optimal randomized acceptor for graph nonisomorphism, Circuit lower bounds in bounded arithmetics, Proof systems that take advice, On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography, Feasibly constructive proofs of succinct weak circuit lower bounds, Polynomial time ultrapowers and the consistency of circuit lower bounds, Induction rules in bounded arithmetic, Do there exist complete sets for promise classes?, Unprovability of circuit upper bounds in Cook's theory PV, Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes, A Tight Karp-Lipton Collapse Result in Bounded Arithmetic, Nondeterministic Instance Complexity and Proof Systems with Advice, On the correspondence between arithmetic theories and propositional proof systems – a survey, Does Advice Help to Prove Propositional Tautologies?

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