ECCC-Report TR01-044https://eccc.weizmann.ac.il/report/2001/044Comments and Revisions published for TR01-044en-usThu, 21 Jun 2001 11:10:21 +0300
Paper TR01-044
| On reducibility and symmetry of disjoint NP-pairs |
Pavel Pudlak
https://eccc.weizmann.ac.il/report/2001/044We 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.
Thu, 21 Jun 2001 11:10:21 +0300https://eccc.weizmann.ac.il/report/2001/044