Consequences of the provability of NP ⊆ P/poly

DOI10.2178/jsl/1203350791zbMath1133.03035OpenAlexW2087012565MaRDI 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 arithmeticnonuniform complexity classescollapse of the polynomial hierarchyproof systems with advice

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (16)

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

This page was built for publication: Consequences of the provability of NP ⊆ P/poly