Nondeterministic functions and the existence of optimal proof systems

DOI10.1016/j.tcs.2009.05.021zbMath1171.68010OpenAlexW1996110613WikidataQ57950025 ScholiaQ57950025MaRDI QIDQ837177

Johannes Köbler, Jochen Messner, Olaf Beyersdorff

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/74439/2/sat_journal_rev_lncs.pdf

zbMATH Keywords

optimal proof systemsdisjoint NP-pairsnondeterministic functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (8)

Soft Subdivision Search in Motion Planning, II: Axiomatics ⋮ Further oracles separating conjectures about incompleteness in the finite domain ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Total nondeterministic Turing machines and a p-optimal proof system for SAT ⋮ An oracle separating conjectures about incompleteness in the finite domain ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle ⋮ Do there exist complete sets for promise classes?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Canonical disjoint NP-pairs of propositional proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Tuples of disjoint \(\mathsf{NP}\)-sets
• On some natural complete operators
• Complexity and structure
• Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
• The monotone circuit complexity of Boolean functions
• The complexity of optimization problems
• On gamma-reducibility versus polynomial time many-one reducibility
• Relative complexity of checking and evaluating
• A hierarchy based on output multiplicity
• A taxonomy of complexity classes of functions
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Optimal proof systems imply complete sets for promise classes
• On reducibility and symmetry of disjoint NP pairs.
• Inverting onto functions.
• Separability and one-way functions
• Non-automatizability of bounded-depth Frege proofs
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• Does the polynomial hierarchy collapse if onto functions are invertible?
• Reductions between disjoint NP-pairs
• Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The Informational Content of Canonical Disjoint NP-Pairs
• On the correspondence between arithmetic theories and propositional proof systems – a survey
• Quantitative Relativizations of Complexity Classes
• Complexity Measures for Public-Key Cryptosystems
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• The relative efficiency of propositional proof systems
• Structure in Approximation Classes
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Oracles That Compute Values
• On Interpolation and Automatization for Frege Systems
• UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
• Disjoint NP-Pairs
• NONDETERMINISTICALLY SELECTIVE SETS
• On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
• The Deduction Theorem for Strong Propositional Proof Systems

This page was built for publication: Nondeterministic functions and the existence of optimal proof systems