Paper Info
Title
Nondeterministic functions and the existence of optimal proof systems
Abstract
We provide new characterizations of two previously studied questions on nondeterministic function classes: Q1: Do nondeterministic functions admit efficient deterministic refinements? Q2: Do nondeterministic function classes contain complete functions? We show that Q1 for the class NPMV"t is equivalent to the question whether the standard proof system for SAT is p-optimal, and to the assumption that every optimal proof system is p-optimal. Assuming only the existence of a p-optimal proof system for SAT, we show that every set with an optimal proof system has a p-optimal proof system. Under the latter assumption, we also obtain a positive answer to Q2 for the class NPMV"t. An alternative view on nondeterministic functions is provided by disjoint sets and tuples. We pursue this approach for disjoint NP-pairs and its generalizations to tuples of sets from NP and coNP with disjointness conditions of varying strength. In this way, we obtain new characterizations of Q2 for the class NPSV. Question Q1 for NPSV is equivalent to the question of whether every disjoint NP-pair is easy to separate. In addition, we characterize this problem by the question of whether every propositional proof system has the effective interpolation property. Again, these interpolation properties are intimately connected to disjoint NP-pairs, and we show how different interpolation properties can be modeled by NP-pairs associated with the underlying proof system.
Year
DOI
Venue
2009
10.1016/j.tcs.2009.05.021
Theor. Comput. Sci.
Keywords
DocType
Volume
nondeterministic functions,Nondeterministic function,optimal proof systems,p-optimal proof system,nondeterministic function class,Nondeterministic functions,disjoint np-pairs,disjoint NP-pair,new characterization,propositional proof system,Optimal proof systems,Disjoint NP -pairs,underlying proof system,optimal proof system,nondeterministic function,class NPMV,standard proof system
Journal
410
Issue
ISSN
Citations 
38-40
Theoretical Computer Science
9
PageRank 
References 
Authors
0.56
44
3
Name
Order
Citations
PageRank
Olaf Beyersdorff122330.33
Johannes Köbler258046.51
Jochen Messner3704.86