24
$\begingroup$

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

$\endgroup$
  • $\begingroup$ See also mathoverflow.net/questions/34889/… $\endgroup$ – Jukka Suomela Aug 16 '10 at 22:10
  • $\begingroup$ 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. $\endgroup$ – Marcos Villagra Aug 16 '10 at 22:13
  • $\begingroup$ Actually, I asked the same question as a comment in that link, but I wanted to make it a real question. $\endgroup$ – Marcos Villagra Aug 16 '10 at 22:15
  • 2
    $\begingroup$ Yes, I know that you know, but the mathoverflow page provides useful background information for others. $\endgroup$ – Jukka Suomela Aug 16 '10 at 22:22
18
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Marcos Villagra Aug 18 '10 at 23:29
  • $\begingroup$ 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. (Link is for fun. ;)) $\endgroup$ – Daniel Apon Aug 19 '10 at 3:57
  • $\begingroup$ Note: It is still considered unlikely that the situation I described above as conceivable is the case for the same reasons in the answer. $\endgroup$ – Daniel Apon Aug 19 '10 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.