Skip to main content

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

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

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

Updated broken link.
Source Link
Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233

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

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

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

LaTeX-ified
Source Link
Daniel Apon
  • 6.1k
  • 1
  • 38
  • 53

This is a (wide) open problem; as in, we know almost nothing. Specifically, because of the trickiness in proving NP \cap coNP$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$NP \cap coNP$-complete problems' existence and add my thoughts:

Currently, we only have "weak," natural candidates for membership in NP \cap coNP - P$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$\le k$, has a randomized time complexity of poly(n)exp(\sqrt{klog(k)})$poly(n) 2^{\sqrt{k log(k)}}$. (If complete problems exist in NP \cap coNP - P$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$P$ iff NP \cap coNP = P$NP \cap coNP = P$, i.e. a completeness result like Cook's theorem for 3SAT and NP$NP$. For NP$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$NP$, we can use non-deterministic Turing machines that halt within a polynomial, p(|x|)$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$PSPACE$ and #P#$P$.

The difficulty, however, with providing a similar representation for NP \cap coNP$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$NP \cap coNP$ with two non-deterministic Turing machines that, purportedly, recognize complementary languages:

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

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

Therefore, M1$M_1$ and M2$M_2$ accept complementary languages iff Miff* $M^*$ does not halt on input x$x$. Therefore, by contradiction, deciding if two polynomial-time Turing machines accept complementary languages is undecidable.

So, the "natural" representation of NP \cap coNP$NP \cap coNP$ problems is not polynomial-time recognizable. The question remains: How do you represent NP \cap coNP$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$NP \cap coNP$. Hence, I claim that the existence of a proof technique that can resolve the completeness of NP \cap coNP$NP \cap coNP$ will be the bigger story here -- not the "automatic" results of NP \cap coNP$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).

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)exp(\sqrt{klog(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 M1 and M2 as follows. On input y, M1 reads the input and always accepts. M2 always rejects unless |y| \ge |x| and M* accepts x in steps \le |y|.

Therefore, M1 and M2 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).

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

edited body
Source Link
Daniel Apon
  • 6.1k
  • 1
  • 38
  • 53
Loading
Source Link
Daniel Apon
  • 6.1k
  • 1
  • 38
  • 53
Loading