Welcome to MathOverflow

Question

8

2

Hi,

Is there any language $L$ know to be complete for $NP \cap co-NP$, i.e. any language $L^{\prime} \in NP\cap co-NP$ reduces in polynomial-time to $L$ and it is known that $L\in NP\cap co-NP$?

Thanks

flag	asked Aug 8 2010 at 4:51 Sid 372●3●9

As far as I can find, there aren't any semantic classes that are known to have complete problems and are not known to be equal to a syntactic class. – Ricky Demer Aug 8 2010 at 5:29

Ryan Williams · Accepted Answer · 2010-08-08 06:31:14Z UTC

$NP \cap coNP$ is not known to have complete languages, but I don't know of any consequences as strong as what Marcos claims. Juris Hartmanis and his students worked extensively on this problem in the early 80's. Two references I know are:

Michael Sipser: On Relativization and the Existence of Complete Sets. ICALP 1982: 523-531

This paper shows that there is an oracle relative to which $NP \cap coNP$ does not have complete sets. So proving that it does have complete sets would at least require non-relativizing techniques. Also, as mentioned by Peter in Marcos' comment, there's also Hartmanis and Immerman's work:

Juris Hartmanis, Neil Immerman: On Complete Problems for NP$\cap$CoNP. ICALP 1985: 250-259

They give several interesting structural results about the problem. For one, they complement Sipser's result, giving an oracle relative to which $NP \cap coNP$ has complete languages yet $P \neq NP \cap coNP \neq NP$. They also show that $NP \cap coNP$ has complete languages under many-one reductions iff it has complete languages under Turing reductions. This paper also cites the following neat characterization by Kowalczyk (1985): $NP \cap coNP$ has a complete language iff there is a recursively enumerable list of pairs of $NP$ machines {$(N_{i,1}, N_{i,2})$} such that $\overline{L(N_{i,1})} = L(N_{i,2})$ and $\bigcup_i L(N_i) = NP \cap coNP$.

But since then, there hasn't been much progress on the question, to my knowledge. I'd be very happy if I were corrected...

Marcos Villagra · Answer 2 · 2010-08-08 06:39:59Z UTC

0

There are no complete problems for $NP\cap coNP$, unless the polynomial hierarchy collapses. You'll find that phrase in several textbooks on complexity theory.

Update: take a look at link talking about this kind of problems. Also, the book by Arora and Barak is a good reference.

Update: The claim above "unless the polynomial hierarchy collapses" is too strong. There is no evidence of such consequence.

A better way to put it would be, there are no problems known to be complete for $NP\cap coNP$. It seems that non-relativizing techniques are required to proof the existence or non-existence of complete sets.

edited Aug 8 2010 at 6:39

answered Aug 8 2010 at 5:48

Marcos Villagra
77●1●7

Got a reference?... – Ryan Williams Aug 8 2010 at 5:54

Please tell me the page on which this is proved in Arora and Barak. – Ryan Williams Aug 8 2010 at 6:01

in the draft version, chapter 5, the polynomial hierarchy and alternations, page 5.2(92), where it says "Note that $\sum_2^p contains both the classes NP and coNP". There is no proof, but this implies that a complete problem collapses the hierarchy to the second level. – Marcos Villagra Aug 8 2010 at 6:05

One would think that any such reference would have to cite Hartmanis and Immerman: springerlink.com/content/w115v82352n00474 but I can't find one that does. – Peter Shor Aug 8 2010 at 6:13

1

Marcos: Of course $Sigma_2 P$ contains $NP$ and $coNP$. That does not mean "$NP \cap coNP$ has a complete language implies the polynomial hierarchy collapses". – Ryan Williams Aug 8 2010 at 6:15

show 3 more comments

A language complete for NP intersection co-NP

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.