Solving satisfiability by Bayesian inference

2012/05/30 by M. Feldmann, Feldmann, Michel
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.48550/arxiv.1205.6658

openalex publication_date 2012/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Quantum computing and the entanglement frontier
• Classical description of quantum randomness using stochastic gauge systems
• Finite Automata and Their Decision Problems
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Simulating physics with computers
• An Unsolvable Problem of Elementary Number Theory

Related

• On the complexity of SAT
• Lower bound for the Complexity of the Boolean Satisfiability Problem
• Machine Learning with Guarantees using Descriptive Complexity and SMT Solvers
• A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
• NSNet: A General Neural Probabilistic Framework for Satisfiability Problems