Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-044 | 14th June 2001 00:00

On reducibility and symmetry of disjoint NP-pairs

RSS-Feed




TR01-044
Authors: Pavel Pudlak
Publication: 21st June 2001 11:10
Downloads: 2032
Keywords: 


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.



ISSN 1433-8092 | Imprint