# US 2022/0044097 A1 · Boolean satisfiability problem solving using restricted boltzmann machines

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0044097 A1
- Document ID: US20220044097A1
- Status: Published application
- Kind: A1
- Application number: 17/390,512
- Filed: 2021-07-30
- Published: 2022-02-10
- Earliest claimed: 2020-08-04
- Assignees: DeepMind Technologies Limited
- Applicants: DeepMind Technologies Limited
- Inventors: Xujie Si; Vinod Nair; Yujia Li; Felix Axel Gimeno Gil
- Web page: https://patentgrep.com/patent/US20220044097A1

## CPC

- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/045: Combinations of networks
- G06N 3/047: Probabilistic or stochastic networks
- G06N 3/0475: Generative networks
- G06N 3/0499: Feedforward networks
- G06N 3/08: Learning methods
- G06N 3/09: Supervised learning
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for satisfiability solving for Boolean formulas. One of the methods includes receiving a request to determine whether an input Boolean formula is satisfiable according to a set of satisfiability criteria; processing the input Boolean formula using a formula model that is configured to receive, as input, the input Boolean formula, and to generate, as output, a satisfiability probability distribution over assignments of values to the literals in the clauses of the input Boolean formula; determining whether the input Boolean formula is satisfiable; sampling, using the satisfiability probability distribution, an assignment of values to the literals in the clauses of the input Boolean formula, and determining whether the assignment of values satisfies the set of satisfiability criteria.

## Claims

### Claim 1

A method performed by one or more computers, the method comprising:
receiving a request to determine whether an input Boolean formula is satisfiable according to a set of satisfiability criteria, wherein the input Boolean formula is a conjunction of a plurality of clauses, wherein each clause is a disjunction of one or more literals;
processing the input Boolean formula using a formula model that is configured to receive, as input, the input Boolean formula, and to generate, as output, a satisfiability probability distribution over assignments of values to the literals in the clauses of the input Boolean formula;
determining whether the input Boolean formula is satisfiable according to the set of satisfiability criteria, comprising, at each of one or more sampling iterations:
sampling, using the satisfiability probability distribution, an assignment of values to the literals in the clauses of the input Boolean formula, and
determining whether the assignment of values satisfies the set of satisfiability criteria; and
in response to determining that the input Boolean formula is satisfiable according to the satisfiability problem, sending, in response to the request, an indication that the input Boolean formula is satisfiable.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
obtaining, for each clause, a respective clause model, wherein the clause model is configured to receive, as input, an input clause of a same length as the clause, and to generate, as output, a respective probability distribution over assignments for the clause.

### Claim 3 (depends on 2)

The method of claim 2, further comprising generating the formula model from each obtained clause model.

### Claim 4 (depends on 2)

The method of claim 2,
wherein each clause model is a respective Restricted Boltzmann Machine network comprising a visible layer, a hidden layer, and a plurality of parameter values, the visible layer comprising a number of visible units equal to a number of unique literals for a respective clause for the clause model, and
wherein each visible unit in the visible layer is interconnected to each hidden unit in the hidden layer, wherein each interconnection between the visible unit and a respective hidden unit is weighted according to a respective parameter value of the plurality of parameter values.

### Claim 5 (depends on 2)

The method of claim 2, wherein obtaining, for each clause, the respective clause model, comprises:
training the respective clause model on a training set of possible assignments for the clause.

### Claim 6 (depends on 1)

The method of claim 1,
wherein the formula model has been trained to generate the satisfiability probability distribution that, when sampled,
(i) assigns higher probabilities to assignments that cause the clause to evaluate to true, and
(ii) assigns lower probabilities to assignments that cause the clause to evaluate to false.

### Claim 7 (depends on 3)

The method of claim 3, wherein generating a formula model from each obtained clause model comprises:
concatenating each clause model together, including interconnecting each visible unit of each clause model with each hidden unit of each clause model that is not in the clause model of the visible unit.

### Claim 8 (depends on 1)

The method of claim 1, wherein generating the satisfiability probability distribution from the formula model comprises processing the formula model across a plurality of hardware accelerators.

### Claim 9 (depends on 1)

The method of claim 1, wherein repeatedly sampling assignments of values from the satisfiability probability distribution comprises sampling the assignments using Markov Chain Monte Carlo.

### Claim 10 (depends on 1)

The method of claim 1, wherein repeatedly sampling the assignments of values from the satisfiability probability distribution comprises repeatedly sampling the assignments of values in parallel across a plurality of hardware accelerators.

### Claim 11 (depends on 1)

The method of claim 1, wherein repeatedly sampling the assignments from the satisfiability probability distribution comprises sampling according to a predetermined annealing schedule.

### Claim 12 (depends on 1)

The method of claim 1,
wherein the satisfiability problem is the SAT problem,
wherein determining whether the input Boolean formula is satisfiable according to the satisfiability problem comprises sampling assignments of values from the satisfiability probability distribution until sampling an assignment that causes the input Boolean formula to evaluate to true, or until reaching a predetermined condition; and
wherein the indication that the input Boolean formula is satisfiable comprises a satisfying assignment.

### Claim 13 (depends on 1)

The method of claim 1, wherein the satisfiability problem is the MAX-SAT problem.

### Claim 14 (depends on 1)

The method of claim 1, wherein the satisfiability problem is the #SAT problem, and wherein determining whether the input Boolean formula is satisfiable according to the satisfiability problem comprises enumerating a plurality of assignments of values that cause the input Boolean formula to evaluate to true by performing the following:
maintaining a list of sampled assignments of values that cause the input Boolean formula to evaluate to true;
whenever sampling an assignment of values that causes the input Boolean formula to evaluate to true, adding the assignment to the list of sampled assignments.

### Claim 15 (depends on 12)

The method of claim 12, wherein sampling the assignments of values comprises sampling the assignments using annealed importance sampling.

### Claim 16 (depends on 1)

The method of claim 1, wherein the predetermined condition is one of (i) a threshold number of samples from the satisfiability probability distribution or (ii) a predetermined time period, and wherein the method further comprises:
in response to reaching the predetermined condition before determining that the input Boolean formula is satisfiable, sending, in response to the request, an indication that the input Boolean formula is not satisfiable.

### Claim 17

A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising:
receiving a request to determine whether an input Boolean formula is satisfiable according to a set of satisfiability criteria, wherein the input Boolean formula is a conjunction of a plurality of clauses, wherein each clause is a disjunction of one or more literals;
processing the input Boolean formula using a formula model that is configured to receive, as input, the input Boolean formula, and to generate, as output, a satisfiability probability distribution over assignments of values to the literals in the clauses of the input Boolean formula;
determining whether the input Boolean formula is satisfiable according to the set of satisfiability criteria, comprising, at each of one or more sampling iterations:
sampling, using the satisfiability probability distribution, an assignment of values to the literals in the clauses of the input Boolean formula, and
determining whether the assignment of values satisfies the set of satisfiability criteria; and
in response to determining that the input Boolean formula is satisfiable according to the satisfiability problem, sending, in response to the request, an indication that the input Boolean formula is satisfiable.

### Claim 18 (depends on 17)

The system of claim 17, the operations further comprising:
obtaining, for each clause, a respective clause model, wherein the clause model is configured to receive, as input, an input clause of a same length as the clause, and to generate, as output, a respective probability distribution over assignments for the clause.

### Claim 19 (depends on 18)

The system of claim 18, the operations further comprising generating the formula model from each obtained clause model.

### Claim 20

One or more non-transitory computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
receiving a request to determine whether an input Boolean formula is satisfiable according to a set of satisfiability criteria, wherein the input Boolean formula is a conjunction of a plurality of clauses, wherein each clause is a disjunction of one or more literals;
processing the input Boolean formula using a formula model that is configured to receive, as input, the input Boolean formula, and to generate, as output, a satisfiability probability distribution over assignments of values to the literals in the clauses of the input Boolean formula;
determining whether the input Boolean formula is satisfiable according to the set of satisfiability criteria, comprising, at each of one or more sampling iterations:
sampling, using the satisfiability probability distribution, an assignment of values to the literals in the clauses of the input Boolean formula, and
determining whether the assignment of values satisfies the set of satisfiability criteria; and
in response to determining that the input Boolean formula is satisfiable according to the satisfiability problem, sending, in response to the request, an indication that the input Boolean formula is satisfiable.
