23
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Very interesting question. I would be surprised if there is a known algorithm to efficiently perform any of these tasks. $\endgroup$ – Giorgio Camerani Sep 2 '13 at 17:33
12
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ This is mentioned in the intro to Generating satisfiable problem instances, by D Achlioptas, C Gomes, H Kautz, B Selman. $\endgroup$ – Colin McQuillan Sep 4 '13 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.