Counting the number of solutions in satisfiability problems with tensor-network message passing.

Area of Science:

• Theoretical Computer Science
• Statistical Physics
• Combinatorial Optimization

Background:

• The Boolean satisfiability (SAT) problem is a core challenge in computer science with broad applications.
• Counting SAT solutions is computationally difficult, often approximated by calculating problem entropy.

Purpose of the Study:

• To propose a novel method for accurately computing the entropy of SAT problems, thereby estimating the number of solutions.
• To enhance solution counting by incorporating effects of both short and long loops in factor graphs.

Main Methods:

• The study converts SAT problems into spin-glass models in statistical physics.
• A new entropy computation method combines tensor network techniques with message-passing algorithms.
• The approach analyzes factor graph structures, including complex loop dependencies.

Main Results:

• The proposed method demonstrated higher accuracy in estimating the number of solutions for 3-SAT problems compared to standard belief propagation algorithms.
• Validation was performed on both random and structured graph instances of 3-SAT.
• The method effectively accounts for intricate loop structures in the problem's factor graph.

Conclusions:

• The novel tensor network and message-passing combination provides a more accurate way to count SAT solutions.
• This method has potential applications in various combinatorial optimization problems.
• The approach advances the understanding and computational tractability of hard computational problems.