ECCC-Report TR05-123https://eccc.weizmann.ac.il/report/2005/123Comments and Revisions published for TR05-123en-usFri, 04 Nov 2005 15:10:27 +0200
Paper TR05-123
| Tuples of Disjoint NP-Sets |
Olaf Beyersdorff
https://eccc.weizmann.ac.il/report/2005/123 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.
Fri, 04 Nov 2005 15:10:27 +0200https://eccc.weizmann.ac.il/report/2005/123