eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/6510
Title:  On Complete Problems for NP$\cap$CoNP 
Authors:  Hartmanis, Juris Immerman, Neil 
Keywords:  computer science technical report 
Issue Date:  Apr1985 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85670 
Abstract:  It is not known whether complete languages exist for $NP\cap CoNP$, and Sipser has shown that there are relativizations so that $NP\cap CoNP$ has no $\leq ^{P}_{m}$complete languages. In this paper we show that $NP\cap CoNP$ has $\leq ^{P}_{m}$complete languages if and only if it has $\leq ^{P}_{T}$complete languages. Furthermore, we show that if a complete language $L_{0}$ exists for $NP\cap CoNP$ and $NP\cap CoNP \neq NP$ then the reduction of $L(N_{i}) \in NP\cap CoNP$ cannot be effectively computed from $N_{i}$. We extend the relativization results by exhibiting an oracle $E$ such that $P^{E} \neq NP^{E} \cap CoNP^{E} \neq NP^{E}$ and for which there exist complete languages in the intersection. For this oracle the reduction to a complete language can be effectively computed from complementary pairs of machines $(N_{i}, N_{j})$ such that $L(N_{i})= \overline{L(N_{j})}$. On the other hand, there also exist oracles $F$ such that $P^{F} \neq NP^{F} \cap CoNP^{F} \neq NP^{F}$ for which the intersection has complete languages, but the reductions to the complete language cannot be effectively computable from the complementary pairs of machines. In this case, the reductions can be computed from $(N_{i}, N_{j}$, Proof that $L(N_{i})= \overline{L(N_{j})}).$ 
URI:  http://hdl.handle.net/1813/6510 
Appears in Collections:  Computer Science Technical Reports Hartmanis, Juris

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
