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
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)
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