Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-123 | 25th October 2005 00:00

Tuples of Disjoint NP-Sets

RSS-Feed




TR05-123
Authors: Olaf Beyersdorff
Publication: 4th November 2005 15:10
Downloads: 3084
Keywords: 


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.



ISSN 1433-8092 | Imprint