Consequences of Complete problems for NP intersects coNP

Question

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

Answer 1

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). 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)}}$. (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).