Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-123 | 25th October 2005 00:00

Tuples of Disjoint NP-Sets


Authors: Olaf Beyersdorff
Publication: 4th November 2005 15:10
Downloads: 3018


Disjoint NP-pairs are a well studied complexity theoretic concept with
important applications in cryptography and propositional proof

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.

ISSN 1433-8092 | Imprint