A new arXiv preprint claims to crack a famously hard AI inference problem, then casually claims to resolve one of math's biggest open questions too.
The paper proposes a polynomial time algorithm for exact marginal inference in Markov random fields, a type of probabilistic model used across AI and computer vision to represent variables that depend on their neighbors. Marginal inference means calculating the probability of one variable after accounting for everyone connected to it, and for large models that is normally a hard combinatorial problem researchers solve only approximately. The author says a purely linear algebraic method can recover the exact answer using just a polynomial number of local marginals or Fourier frequencies, rather than the exponential blowup that plagues standard approaches. The paper is the third posted revision (v3) of a preprint originally submitted under the arXiv identifier 1709.09051, and it closes with a single sentence claiming the result also settles P versus NP.
Exact, efficient marginal inference would matter to anyone building probabilistic models in vision, genetics, or robotics, where approximations are the current workaround. But that is not the headline claim here. The paper's offhand assertion that it also resolves P versus NP, one of the most famous open problems in mathematics and computer science, is the kind of claim that normally arrives with extraordinary scrutiny attached, not a single closing sentence.
A preprint settling P versus NP in its last line, three revisions deep and nine years after it first appeared, is not how landmark proofs usually get announced.