Nondeterministic functions and the existence of optimal proof systems
type: Item
instance of: scholarly article
title: Nondeterministic functions and the existence of optimal proof systems
zbMATH Open document ID: 1171.68010
author: Olaf Beyersdorff
author: Johannes Köbler
author: Jochen Messner
published in: Theoretical Computer Science
publication date: 2009-09-10T00:00:00Z
full work available at URL: sat journal rev lncs.pdf
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5602744
zbMATH Keywords: optimal proof systems
zbMATH Keywords: nondeterministic functions
zbMATH Keywords: disjoint NP-pairs
Wikidata QID: Q57950025
MaRDI profile type: Publication
OpenAlex ID: W1996110613
cites work: The monotone circuit complexity of Boolean functions
cites work: Q4321931
cites work: The Deduction Theorem for Strong Propositional Proof Systems
cites work: Classes of representable disjoint \textsf{NP}-pairs
cites work: Tuples of disjoint \(\mathsf{NP}\)-sets
cites work: On the correspondence between arithmetic theories and propositional proof systems – a survey
cites work: Non-automatizability of bounded-depth Frege proofs
cites work: Lower bounds for cutting planes proofs with small coefficients
cites work: On Interpolation and Automatization for Frege Systems
cites work: Quantitative Relativizations of Complexity Classes
cites work: Does the polynomial hierarchy collapse if onto functions are invertible?
cites work: The relative efficiency of propositional proof systems
cites work: Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory
cites work: Structure in Approximation Classes
cites work: Inverting onto functions.
cites work: Oracles That Compute Values
cites work: Separability and one-way functions
cites work: Reductions between disjoint NP-pairs
cites work: Disjoint NP-Pairs
cites work: Canonical disjoint NP-pairs of propositional proof systems
cites work: The Informational Content of Canonical Disjoint NP-Pairs
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Q4452100
cites work: NONDETERMINISTICALLY SELECTIVE SETS
cites work: On some natural complete operators
cites work: Optimal proof systems imply complete sets for promise classes
cites work: UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
cites work: Q4856172
cites work: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
cites work: Propositional proof systems, the consistency of first order theories and the complexity of computations
cites work: Some consequences of cryptographical conjectures for \(S_2^1\) and EF
cites work: The complexity of optimization problems
cites work: On gamma-reducibility versus polynomial time many-one reducibility
cites work: Q4251070
cites work: Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
cites work: A hierarchy based on output multiplicity
cites work: Q3221403
cites work: Lower bounds for resolution and cutting plane proofs and monotone computations
cites work: Q4215637
cites work: On reducibility and symmetry of disjoint NP pairs.
cites work: Q4375799
cites work: Q3758729
cites work: On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
cites work: Q4263798
cites work: On an optimal propositional proof system and the structure of easy subsets of TAUT.
cites work: Q5422270
cites work: Complexity and structure
cites work: A taxonomy of complexity classes of functions
cites work: Relative complexity of checking and evaluating
cites work: #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
DOI: 10.1016/J.TCS.2009.05.021
Recommended article: Q4364366
Recommended article: Optimal Proofs of Determinacy
Recommended article: Q5422270
Recommended article: Nondeterministic Instance Complexity and Proof Systems with Advice
Recommended article: OPTIMAL PROOFS OF DETERMINACY II
Recommended article: Q4825686
Recommended article: Partiality and nondeterminacy in program proofs
Recommended article: Q4251070

Nondeterministic functions and the existence of optimal proof systems (Recommended article)
Recommended article: Q4501542
Similarity Score: 0.8755745
Recommender Run: Recommender Run 3

Nondeterministic functions and the existence of optimal proof systems (Recommended article)
Recommended article: Q4381398
Similarity Score: 0.8740586
Recommender Run: Recommender Run 3