5
$\begingroup$

I need an instance of 3SAT with exactly one solution but I cannot think of or find one anywhere. Can anyone please give me an example?

$\endgroup$
0
13
$\begingroup$

Try this: $$ (A \lor B \lor C) \land (A \lor B \lor \lnot C) \land (A \lor \lnot B \lor C) \land (A \lor \lnot B \lor \lnot C) \land (\lnot A \lor B \lor C) \land (\lnot A \lor B \lor \lnot C) \land (\lnot A \lor \lnot B \lor C) $$

$\endgroup$
0
20
$\begingroup$

The empty 3SAT instance (over no variables) has one solution.

$\endgroup$
1
  • 23
    $\begingroup$ Fitting username. $\endgroup$
    – qwr
    Feb 20 at 6:59
16
$\begingroup$

If you are seeking a formula with 3 variables $x$, $y$, $z$, then you can consider clauses $(\ell_x \vee \ell_y \vee \ell_z)$ where $\ell_x$ is either $x$ or $\neg x$ (and same thing for $\ell_y$ and $\ell_z$). There is a total of 8 such clauses. If you consider a conjunction of all 8 clauses and remove exactly one of them, you get a 3-CNF formula with exactly one solution.

For exemple, if you remove the clause $(\neg x \vee y\vee z)$, then the solution to the formula is given by $x = \top$, $y = \bot$ and $z = \bot$.

$\endgroup$
9
$\begingroup$

One variable: $(A \lor A \lor A)$

$\endgroup$
3
$\begingroup$

Just about every puzzle game can be formulated as a 3SAT with a unique solution. Sudoku is perhaps the canonical example.

$\endgroup$
1
  • 7
    $\begingroup$ You have to be careful, though, that the conversion from SAT to 3SAT maintains this property. $\endgroup$ Feb 20 at 0:13
3
$\begingroup$

Semiprime factoring.

Define an unsigned integer multiplication circuit such that X * Y = P.

Define P as a constant equal to an arbitrary semiprime number (there are an infinity of such numbers).

Define X and Y as free variables such that they have one less bit than P (to ban the solution 1 * P and P * 1).

Add the constraint that X <= Y (to ban the solution Y * X).

Convert the multiplication circuit to a 3SAT formula (clauses for each OR,AND,XOR gate, each gate of the circuit should have 3 variables, then the clauses ban the incorrect combinations). The bits of P are unit clauses.

The only way to satisfy this formula is to put X and Y in the right order as the input. Just like in the circuit, the rest of the formula is defined by the input. By the mathematical definition of a semiprime number, there no other way to obtain P through multiplication except by multiplying X and Y, or 1 and itself.

Depending on your goals, this is a convenient approach because you can generate an infinity of random formulas with unique solution.

(However, the formula's unique solution should be exponentially hard to solve in the size of P, because multiplication is considered a one-way function.)

$\endgroup$

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.