A polynomial time algebraic solution to exact marginal inference in Markov Random Field models

Abstract:This paper develops on algebraic grounds a polynomial time exact linear solution to the hard combinatorial problem of marginal inference in Markov random field (MRF) models under general assumptions. To prove our claim, we first implicitly remodel a MRF joint distribution as the unique solution of some linear identity assuming its clique potential functions (equivalently, its individual conditional distributions) to be specified. Then, by assuming an arbitrary point subset, we relax accordingly such a (global) linear identity for deriving a second linear identity, solely, acting on a polynomial time number of entries (e.g.; local marginals or Fourier frequencies) of a solution. Then, we show, only using linear algebraic techniques, that such an identity enables to capture all the entries necessary for the exact reconstruction of an MRF marginal distribution, thus, allowing to solve for the latter, exactly and in polynomial time, using a standard linear solver. Last, but not least, this paper probably solves, once and for all, the P = NP conjecture.

Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Combinatorics (math.CO)

G.1.6; G.2.1; G.2.2

arXiv:1709.09051 [math.OC]

(or arXiv:1709.09051v3 [math.OC] for this version)

https://doi.org/10.48550/arXiv.1709.09051 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.