1. Tuples of Disjoint $\mathsf{NP}$ -Sets.
- Author
-
Beyersdorff, Olaf
- Subjects
DATA encryption ,CRYPTOGRAPHY ,SYMBOLISM ,SIGNS & symbols ,MATHEMATICAL analysis ,MATHEMATICS ,ALGEBRA ,COMBINATORICS ,NUMERICAL analysis ,ASYMPTOTIC expansions - Abstract
Disjoint $\mathsf{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 $\mathsf{NP}$ -pairs to disjoint k-tuples of $\mathsf{NP}$ -sets for k≥2. We define subclasses of the class of all disjoint k-tuples of $\mathsf{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 $\mathsf{NP}$ -pairs exist if and only if complete disjoint k-tuples of $\mathsf{NP}$ -sets exist for all k≥2. 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. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF