O. 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>1. 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>1. 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-File: Tuples of disjoint NP-sets