Solving satisfiability by Bayesian inference

Abstract

We demonstrate that any logical problem can be solved by Bayesian inference. In this approach, the distinction between complexity classes vanishes. The method is illustrated by solving the 3-SAT problem in polynomial time. Beyond this, Bayesian inference could be the background of artificial neural network theory.

This version V5: Editorial revisions. 11 pages, no figure. (Initial title:From classical versus quantum algorithms to P versus NP). Additional comments on relations with quantum computing in arXiv: 1312.7551

References in corpus (4)

• Quantum Computing
• Quantum computing and the entanglement frontier
• The P versus NP Problem
• Classical description of quantum randomness using stochastic gauge systems

Cited by in corpus (1)

• Polynomial time factoring algorithm using Bayesian arithmetic