<p>There is a simple algorithm for V3.
I'll use the convention that there are $(2n)^3$ possible clauses,
so $2^{8n^3}$ formulas.
(This is just for simplicity - if you don't want all $8n^3$ clauses to be considered valid, it wouldn't affect the following argument.)</p>

<p>Pick a random assignment from $\{0,1\}^n$.
For each of the $7n^3$ possible clauses that are true on this assignment,
include the clause with probability $1/2$.
Each formula $\phi$ will appear with probability proportional to
its number of satisfying assignments.
The $m$-clause variant is similar: pick a set of size $m$
out of the $7n^3$ clauses.</p>

CC BY-SA 3.0
2013-09-04T09:45:15.613Z
This is mentioned in the intro to *Generating satisfiable problem instances*, by
D Achlioptas, C Gomes, H Kautz, B Selman.
Colin McQuillan
CC BY-SA 3.0
2013-09-04T09:34:33.350Z
2013-09-04T09:34:33.350Z
Colin McQuillan
<p>Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned on the formula being satisfiable: </p>

<p>Q1: Can this be achieved efficiently by a classical computer (with random bits)? </p>

<p>Q2: Can this be achieved efficiently by a quantum computer? </p>

<p>I am also interested in the following two variants:</p>

<p>V2: You sample all the formulas w.r.t. a probability distribution that gives satisfiable formulas twice the weight of unsatisfiable formulas.</p>

<p>V3: you sample where the weight is the number of satisfying assignments (Here we care only about Q2).</p>

<p><strong>Update:</strong> Colins' answer demonstrates a simple algorithm for V3. (I was wrong in assuming that this is classically difficult.) Let me mention another variant
of all the three questions: </p>

<p><strong>You specify in advance $m$ clauses and you need to sample random satisfiable subsets of the input clauses.</strong></p>

CC BY-SA 3.0
2013-09-02T17:33:47.873Z
Very interesting question. I would be surprised if there is a known algorithm to efficiently perform any of these tasks.
Giorgio Camerani
<cc.complexity-theory><quantum-computing><sample-complexity>
Sampling satisfiable 3-SAT formulas
Gil Kalai
# Sampling satisfiable 3-SAT formulas

(Asked by: username_0 on 2013-09-01)

Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned on the formula being satisfiable:

Q1: Can this be achieved efficiently by a classical computer (with random bits)?

Q2: Can this be achieved efficiently by a quantum computer?

I am also interested in the following two variants:

V2: You sample all the formulas w.r.t. a probability distribution that gives satisfiable formulas twice the weight of unsatisfiable formulas.

V3: you sample where the weight is the number of satisfying assignments (Here we care only about Q2).

**Update:** Colins' answer demonstrates a simple algorithm for V3. (I was wrong in assuming that this is classically difficult.) Let me mention another variant
of all the three questions:

**You specify in advance $m$ clauses and you need to sample random satisfiable subsets of the input clauses.**

**Tags:** cc.complexity-theory, quantum-computing, sample-complexity
> **Comments:**
> **username_1**: Very interesting question. I would be surprised if there is a known algorithm to efficiently perform any of these tasks.  

---

## 1 answers

### Answer by username_2 on 2013-09-04. Score: 12

There is a simple algorithm for V3.
I'll use the convention that there are $(2n)^3$ possible clauses,
so $2^{8n^3}$ formulas.
(This is just for simplicity - if you don't want all $8n^3$ clauses to be considered valid, it wouldn't affect the following argument.)

Pick a random assignment from $\{0,1\}^n$.
For each of the $7n^3$ possible clauses that are true on this assignment,
include the clause with probability $1/2$.
Each formula $\phi$ will appear with probability proportional to
its number of satisfying assignments.
The $m$-clause variant is similar: pick a set of size $m$
out of the $7n^3$ clauses.

> **Comments:**
> **username_2**: This is mentioned in the intro to *Generating satisfiable problem instances*, by D Achlioptas, C Gomes, H Kautz, B Selman.  

---

