Simplifying random satisfiability problems by removing frustrating interactions

How can we remove some interactions (generate shorter clauses) in a constraint satisfaction problem (CSP) such that it still remains satisfiable? In this paper we study a modified survey propagation algorithm that enables us to address this question for a prototypical CSP, i.e., random $K$-satisfiability problem. The average number of removed interactions is controlled by a tuning parameter in the algorithm. If the original problem is satisfiable then we are able to construct satisfiable subproblems ranging from the original one to a minimal one with minimum possible number of interactions. The minimal satisfiable subproblems will directly provide the solutions of the original problem.

Figure 1

Factor graph representation of the problem. Squares and circles denote function and variable nodes, respectively.

Figure 2

Convergence probability for two values of $\alpha$ close to the SAT-UNSAT transition. Number of variables is $N=1000$ and statistical errors are of order 0.01.

Figure 3

Convergence probability for different problem sizes at $\alpha =4.2$. Statistical errors are of order 0.01.

Figure 4

The average weight and its standard deviation for $N=1000$. Statistical errors are about the size of the points.

Figure 5

Estimated value of the number of members in $G_{\mu }$. The results are for $N=1000$ and statistical errors are of order 0.1.

Figure 6

Average entropy of a subproblem in $G_{\mu }$ for $N=1000$. Statistical errors are about the size of the points.

Figure 7

Average complexity of a subproblem in $G_{\mu }$ for $N=1000$. Statistical errors are about the size of the points.

Figure 8

Satisfiability probability of maximum spanning trees vs $\mu$. The problem size is $N=1000$ and statistical errors are of order 0.01.

Figure 9

Satisfiability probability of maximum spanning trees for a few problem sizes. Statistical errors are of order 0.01.

Figure 10

Entropy of typical satisfiable spanning trees for $N=1000$ and $\mu =0.04$.

Figure 11

Degree distribution of variable nodes in satisfiable and random spanning trees. The parameters are $N=1000$, $\alpha =4.2$, and $\mu =0.025$. Statistical errors are about the size of the points.

Figure 12

Average diameter of satisfiable and random spanning trees for $N=1000$ and $\mu =0.05$.

Figure 13

Satisfiability probability of a minimal subproblem vs $\mu$. Number of variables is $N=1000$ and statistical errors are of order 0.01.

Figure 14

Satisfiability probability of minimal subproblems at $\alpha =4.2$. Statistical errors are of order 0.01.

Figure 15

Fraction of the free variables in the minimal satisfiable subproblems. Number of variables is $N=1000$ and statistical errors are of order 0.001.

Figure 16

Comparing degree distribution of the variable nodes in satisfiable and random minimal subproblems. Number of variable nodes is $N=1000$ and statistical errors are of order 0.01.