Submit progress

on The NP versus coNP Problem

The statement

Let $P$ denote the class of decision problems solvable in polynomial time by a deterministic Turing machine. Let $NP$ denote the class of decision problems for which there exists a polynomial $p$ over $\mathbb{N}$ and a polynomial-time computable relation $R$ on pairs of binary strings such that, for every input string $x$ , the problem answers "yes" on $x$ if and only if there exists a witness string $w$ with $|w| \leq p(|x|)$ for which $R(x,w)$ holds. Let $coNP$ denote the class of decision problems whose complements belong to $NP$ . Does $NP \neq coNP$ ?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.