24

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.

Gil Kalai
  • 6,033
  • 35
  • 73

1 Answers1

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.

Colin McQuillan
  • 3,546
  • 22
  • 29