Submit progress

on The P versus NP Problem

The statement

Let a decision problem be a function from lists of booleans to booleans. A complexity class is a set of decision problems. A function is computable in polynomial time if there exists a deterministic Turing machine that computes it in time polynomial in the input length. The complexity class P is the set of decision problems computable in polynomial time by a deterministic Turing machine. The complexity class NP is the set of decision problems for which there exists a polynomial $p$ over $\mathbb{N}$ and a polynomial-time computable relation $R : (\text{List } \text{Bool} \times \text{List } \text{Bool}) \to \text{Bool}$ such that for all inputs $x$ , the decision problem accepts $x$ if and only if there exists a witness $w$ with $|w| \leq p(|x|)$ such that $R(x, w)$ holds. Prove that $\mathsf{P} \neq \mathsf{NP}$ .

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.