Tuples of Disjoint NP-Sets
Olaf Beyersdorff
Abstract:
Disjoint NP-pairs are a well studied complexity-theoretic concept with
important applications in cryptography and propositional proof
complexity. In this paper we introduce a natural generalization of the
notion of disjoint NP-pairs to disjoint k-tuples of NP-sets for k ≥ 2.
We define subclasses of the class of all disjoint k-tuples of NP-sets.
These subclasses are associated with a propositional proof system and
possess complete tuples which are defined from the proof system.
In our main result we show that complete disjoint NP-pairs exist if
and only if complete disjoint k-tuples of NP-sets exist for all k ≥ 2.
Further, this is equivalent to the existence of a propositional proof
system in which the disjointness of all k-tuples is shortly provable.
We also show that a strengthening of this conditions characterizes the
existence of optimal proof systems.
PDF: tuples_journal.pdf