__
TR01-044 | 14th June 2001 00:00
__

#### On reducibility and symmetry of disjoint NP-pairs

**Abstract:**
We consider some problems about pairs of disjoint $NP$ sets.

The theory of these sets with a natural concept of reducibility

is, on the one hand, closely related to the theory of proof

systems for propositional calculus, and, on the other, it

resembles the theory of NP completeness. Furthermore, such

pairs are important in cryptography. Among others, we prove that

the Broken Mosquito Screen pair of disjoint $NP$-sets can be

polynomially reduced to Clique-Coloring pair and thus is

polynomially separable and we show that the pair of disjoint

NP-sets canonically associated with the Resolution proof system

is symmetric.