<p>This is a (wide) open problem; as in, we know almost nothing. Specifically, because of the trickiness in <em>proving</em> <span class="math-container">$NP \cap coNP$</span>-complete problems, we need very different proof techniques than currently exist. As such, a discussion of consequences should reasonably include a tangent on "What would it mean to have such powerful, new proof techniques?"</p>

<p>For a relatively recent discussion of the topic, there is David Johnson's 26th NP-Completeness column in the <em>ACM Transactions on Algorithms</em> from 2007 (<a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=D2C93BB7DA98397482AC9804528997A3?doi=10.1.1.84.7884&amp;rep=rep1&amp;type=pdf" rel="noreferrer">PDF</a>). Allow me to paraphrase some of what David says regarding the question of proving <span class="math-container">$NP \cap coNP$</span>-complete problems' existence and add my thoughts:</p>

<p>Currently, we only have "weak," natural candidates for membership in <span class="math-container">$NP \cap coNP - P$</span> in the sense that the strongest <em>evidence</em> for their membership is that we haven't managed to find a polynomial time algorithm for them yet. He lists a couple candidates: SMALL FACTOR, SIMPLE STOCHASTIC GAME, and MEAN PAYOFF GAME. Some of the extra "weirdness" of these problems comes from the best heuristic run times for solving them, e.g. SMALL FACTOR, aka INTEGER FACTOR <span class="math-container">$\le k$</span>, has a randomized time complexity of <a href="http://qwiki.stanford.edu/wiki/Complexity_Garden#integer_factor" rel="noreferrer"><span class="math-container">$poly(n) 2^{\sqrt{k log(k)}}$</span></a>. (If complete problems exist in <span class="math-container">$NP \cap coNP - P$</span>, then <em>is such sub-exponential</em> (neither purely exponential, nor quite polynomial) <em>runtime endemic of the class?</em>)</p>

<p>So specifically, we would want to prove something like: problem A is only in <span class="math-container">$P$</span> iff <span class="math-container">$NP \cap coNP = P$</span>, i.e. a completeness result like Cook's theorem for 3SAT and <span class="math-container">$NP$</span>. For <span class="math-container">$NP$</span>, such proofs universally involve polynomial-time reductions (and fix your favorite, additional restrictions, e.g. Cook-reductions, Karp-reductions). As a result, under polynomial-time reduction techniques, it must be the case that there exists a polynomial-time recognizable representation of the class. For <span class="math-container">$NP$</span>, we can use non-deterministic Turing machines that halt within a polynomial, <span class="math-container">$p(|x|)$</span>, number of steps. As David points out, we have similar representations for other classes (where the status is more clear) such as <span class="math-container">$PSPACE$</span> and <strong>#</strong><span class="math-container">$P$</span>.</p>

<p>The difficulty, however, with providing a similar representation for <span class="math-container">$NP \cap coNP$</span> is that the "natural" analog <em>allows</em> us to embed the Halting Problem within the representation and is therefore <em>undecidable</em>. That is, consider the following attempt to represent <span class="math-container">$NP \cap coNP$</span> with two non-deterministic Turing machines that, purportedly, recognize complementary languages:</p>

<p>Question: Does a Turing Machine <span class="math-container">$M^*$</span> halt on input <span class="math-container">$x \in {0,1}^n$</span>?</p>

<p>Construct two linear-time Turing machines <span class="math-container">$M_1$</span> and <span class="math-container">$M_2$</span> as follows. On input <span class="math-container">$y$</span>, <span class="math-container">$M_1$</span> reads the input and always accepts. <span class="math-container">$M_2$</span> always rejects unless <span class="math-container">$|y| \ge |x|$</span> and <span class="math-container">$M^*$</span> accepts <span class="math-container">$x$</span> in steps <span class="math-container">$\le |y|$</span>.</p>

<p>Therefore, <span class="math-container">$M_1$</span> and <span class="math-container">$M_2$</span> accept complementary languages <em>iff</em> <span class="math-container">$M^*$</span> does not halt on input <span class="math-container">$x$</span>. Therefore, by contradiction, deciding if two polynomial-time Turing machines accept complementary languages is undecidable.</p>

<p>So, the "natural" representation of <span class="math-container">$NP \cap coNP$</span> problems is not polynomial-time recognizable. The question remains: How do you represent <span class="math-container">$NP \cap coNP$</span> problems such that they are polynomial-time recognizable?</p>

<p>There has been no significant work done on this issue, but its successful resolution is necessary to prove completeness in <span class="math-container">$NP \cap coNP$</span>. Hence, I claim that the existence of a proof technique that can resolve the completeness of <span class="math-container">$NP \cap coNP$</span> will be the bigger story here -- not the "automatic" results of <span class="math-container">$NP \cap coNP$</span>-complete problems (e.g. complexity classes, perhaps, collapsing) that we are already aware of (or rather, <em>will be aware of</em>, hypothetically in the future).</p>

CC BY-SA 2.5
2010-08-18T23:29:48.250Z
thanks for the PDF. Haven't read it yet but I will. There is this paper:

"On total functions, existence theorems and computational complexity". Nimrod Megiddo and Christos Papadimitriou. Theoretical Computer Science 81, 1991.

It is not about $NP\cap coNP$, but its associated function class TFNP, i.e. $TFNP=F(NP\cap coNP)$. There is the following theorem:

"There is an FNP-complete problem in TFNP iff NP=coNP".

Given that search and decision problems are polynomially related, does this theorem also extends to $NP\cap coNP$? If so, this will  imply a big collapse in PH. Is this correct?
Marcos Villagra
CC BY-SA 2.5
2010-08-19T03:57:06.650Z
This does not directly translate (in the way I believe you are implying). Note that the theorem is not referring just to ANY complete problem, but an FNP-complete problem. This is equivalent to saying "There is an NP-complete problem in NP \cap coNP iff NP=coNP." As far as I am aware, it is conceivable that NP \cap coNP have complete problems that are distinct from NP-complete problems, without [PH collapsing](http://www.scottaaronson.com/writings/phcollapse.pdf). (Link is for fun. ;))
Daniel Apon
CC BY-SA 2.5
2010-08-19T04:06:38.317Z
Note: It is still considered unlikely that the situation I described above as conceivable is the case for the same reasons in the answer.
Daniel Apon
CC BY-SA 4.0
2010-08-18T16:57:18.573Z
2019-01-04T23:14:00.293Z
2019-01-04T23:14:00.293Z
Daniel Apon
<p>What are the consequences of having complete problems in $NP\cap coNP$?</p>

CC BY-SA 2.5
2010-08-16T22:10:24.773Z
See also http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np
Jukka Suomela
CC BY-SA 2.5
2010-08-16T22:13:10.480Z
I know that link. My question is about the consequences. For example, if language L is complete for $NP\cap coNP$ then PH collapses to the $i$-th level, or something like that.
Marcos Villagra
CC BY-SA 2.5
2010-08-16T22:15:07.623Z
Actually, I asked the same question as a comment in that link, but I wanted to make it a real question.
Marcos Villagra
CC BY-SA 2.5
2010-08-16T22:22:53.167Z
Yes, I know that you know, but the mathoverflow page provides useful background information for others.
Jukka Suomela
<cc.complexity-theory><conditional-results>
Consequences of Complete problems for NP intersects coNP
Marcos Villagra
# Consequences of Complete problems for NP intersects coNP

(Asked by: username_0 on 2010-08-16)

What are the consequences of having complete problems in $NP\cap coNP$?

**Tags:** cc.complexity-theory, conditional-results

> **Comments:**
> **username_1**: See also http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np  
> **username_0**: I know that link. My question is about the consequences. For example, if language L is complete for $NP\cap coNP$ then PH collapses to the $i$-th level, or something like that.  
> **username_0**: Actually, I asked the same question as a comment in that link, but I wanted to make it a real question.  
> **username_1**: Yes, I know that you know, but the mathoverflow page provides useful background information for others.  

---

## 1 answers

### Answer by username_2 on 2010-08-18. Score: 22 | Accepted answer

This is a (wide) open problem; as in, we know almost nothing. Specifically, because of the trickiness in *proving* $NP \cap coNP$-complete problems, we need very different proof techniques than currently exist. As such, a discussion of consequences should reasonably include a tangent on "What would it mean to have such powerful, new proof techniques?"

For a relatively recent discussion of the topic, there is David Johnson's 26th NP-Completeness column in the *ACM Transactions on Algorithms* from 2007 ([PDF](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=D2C93BB7DA98397482AC9804528997A3?doi=10.1.1.84.7884&rep=rep1&type=pdf)). Allow me to paraphrase some of what David says regarding the question of proving $NP \cap coNP$-complete problems' existence and add my thoughts:

Currently, we only have "weak," natural candidates for membership in $NP \cap coNP - P$ in the sense that the strongest *evidence* for their membership is that we haven't managed to find a polynomial time algorithm for them yet. He lists a couple candidates: SMALL FACTOR, SIMPLE STOCHASTIC GAME, and MEAN PAYOFF GAME. Some of the extra "weirdness" of these problems comes from the best heuristic run times for solving them, e.g. SMALL FACTOR, aka INTEGER FACTOR $\le k$, has a randomized time complexity of [$poly(n) 2^{\sqrt{k log(k)}}$](http://qwiki.stanford.edu/wiki/Complexity_Garden#integer_factor). (If complete problems exist in $NP \cap coNP - P$, then *is such sub-exponential* (neither purely exponential, nor quite polynomial) *runtime endemic of the class?*)

So specifically, we would want to prove something like: problem A is only in $P$ iff $NP \cap coNP = P$, i.e. a completeness result like Cook's theorem for 3SAT and $NP$. For $NP$, such proofs universally involve polynomial-time reductions (and fix your favorite, additional restrictions, e.g. Cook-reductions, Karp-reductions). As a result, under polynomial-time reduction techniques, it must be the case that there exists a polynomial-time recognizable representation of the class. For $NP$, we can use non-deterministic Turing machines that halt within a polynomial, $p(|x|)$, number of steps. As David points out, we have similar representations for other classes (where the status is more clear) such as $PSPACE$ and **#**$P$.

The difficulty, however, with providing a similar representation for $NP \cap coNP$ is that the "natural" analog *allows* us to embed the Halting Problem within the representation and is therefore *undecidable*. That is, consider the following attempt to represent $NP \cap coNP$ with two non-deterministic Turing machines that, purportedly, recognize complementary languages:

Question: Does a Turing Machine $M^\*$ halt on input $x \in {0,1}^n$?

Construct two linear-time Turing machines $M\_1$ and $M\_2$ as follows. On input $y$, $M\_1$ reads the input and always accepts. $M\_2$ always rejects unless $|y| \ge |x|$ and $M^\*$ accepts $x$ in steps $\le |y|$.

Therefore, $M\_1$ and $M\_2$ accept complementary languages *iff* $M^\*$ does not halt on input $x$. Therefore, by contradiction, deciding if two polynomial-time Turing machines accept complementary languages is undecidable.

So, the "natural" representation of $NP \cap coNP$ problems is not polynomial-time recognizable. The question remains: How do you represent $NP \cap coNP$ problems such that they are polynomial-time recognizable?

There has been no significant work done on this issue, but its successful resolution is necessary to prove completeness in $NP \cap coNP$. Hence, I claim that the existence of a proof technique that can resolve the completeness of $NP \cap coNP$ will be the bigger story here -- not the "automatic" results of $NP \cap coNP$-complete problems (e.g. complexity classes, perhaps, collapsing) that we are already aware of (or rather, *will be aware of*, hypothetically in the future).

> **Comments:**
> **username_0**: thanks for the PDF. Haven't read it yet but I will. There is this paper:  "On total functions, existence theorems and computational complexity". Nimrod Megiddo and Christos Papadimitriou. Theoretical Computer Science 81, 1991.  It is not about $NP\cap coNP$, but its associated function class TFNP, i.e. $TFNP=F(NP\cap coNP)$. There is the following theorem:  "There is an FNP-complete problem in TFNP iff NP=coNP".  Given that search and decision problems are polynomially related, does this theorem also extends to $NP\cap coNP$? If so, this will  imply a big collapse in PH. Is this correct?  
> **username_2**: This does not directly translate (in the way I believe you are implying). Note that the theorem is not referring just to ANY complete problem, but an FNP-complete problem. This is equivalent to saying "There is an NP-complete problem in NP \cap coNP iff NP=coNP." As far as I am aware, it is conceivable that NP \cap coNP have complete problems that are distinct from NP-complete problems, without [PH collapsing](http://www.scottaaronson.com/writings/phcollapse.pdf). (Link is for fun. ;))  
> **username_2**: Note: It is still considered unlikely that the situation I described above as conceivable is the case for the same reasons in the answer.  

---

