Researcher claims polynomial-time solution to marginal inference in Markov Random Fields

An algebraic method for computing marginal distributions in Markov Random Field (MRF) models has been proposed on arXiv, with claims of achieving polynomial-time exact inference—a problem traditionally considered computationally hard.

The Problem#

Marginal inference in MRF models—extracting individual probability distributions from a joint distribution over many variables—is a longstanding computational bottleneck. Finding exact marginals in general graphical models is known to be NP-hard, making efficient algorithms elusive for practitioners working with complex probabilistic systems.

The Proposed Approach#

The paper recasts the MRF inference problem through an algebraic lens. Rather than relying on conventional graphical or combinatorial methods, the authors reformulate a joint distribution as the unique solution to a linear identity, once clique potential functions are specified. By relaxing this global linear system to operate only on a polynomial-sized subset of variables—such as local marginals or Fourier coefficients—they derive a second linear identity that captures sufficient information for exact reconstruction.

The key insight is showing that standard linear algebra solvers can then directly compute the marginal distribution, circumventing the combinatorial explosion that makes the problem intractable by other means.

Broader Claims#

The submission abstract makes an extraordinary assertion: that the method may settle the P = NP conjecture, one of mathematics' most celebrated open problems. Such claims require rigorous peer review and scrutiny from the broader research community.

The paper has undergone multiple revisions on arXiv since its initial submission in September 2017, with the latest version appearing in September 2026.