__
TR05-123 | 25th October 2005 00:00
__

#### Tuples of Disjoint NP-Sets

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

posses 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.