Skip to main content
Post Made Community Wiki by Todd Trimble
Source Link
Eran
  • 101
  • 1
  • 5

Ladner's theorem states that there exist $\mathsf{NP}$-intermediate problems when $\mathsf{P}\neq\mathsf{NP}$. However, the problem constructed in Ladner's proof is rather 'unnatural'. The question arises of whether any 'natural' examples of problems can be $\mathsf{NP}$-intermediate.

The Dichotomy Conjecture of Feder and Vardi (first stated here) states that, under the assumption that $\mathsf{P}\neq\mathsf{NP}$, the computational problems known as constraint satisfaction problems (CSPs for short) are either $\mathsf{NP}$-complete or belong to $\mathsf{P}$.

The consensus in the community (last I knew) is that Dmitriy Zhuk (https://arxiv.org/abs/1704.01914) and Andrei Bulatov (https://arxiv.org/abs/1703.03021) have independently proven the conjecture to be true. Their proofs cap a decades long approach of applying universal algebra to the question.