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?
$\begingroup$
$\endgroup$
0
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
2
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) $$
answered Feb 18, 2021 at 14:25
-
$\begingroup$ But this isn't NPC in the size of the input? You have 2^n - 1 clauses. Iterate them linearly and check who's missing. $\endgroup$ Commented Oct 1, 2023 at 17:58
-
$\begingroup$ The question asked for an instance of 3SAT with exactly one solution. My answer gives such an instance. $\endgroup$ Commented Oct 29, 2023 at 13:22
$\begingroup$
$\endgroup$
1
The empty 3SAT instance (over no variables) has one solution.
-
31
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
One variable: $(A \lor A \lor A)$
$\begingroup$
$\endgroup$
1
Just about every puzzle game can be formulated as a 3SAT with a unique solution. Sudoku is perhaps the canonical example.
-
7$\begingroup$ You have to be careful, though, that the conversion from SAT to 3SAT maintains this property. $\endgroup$ Commented Feb 20, 2021 at 0:13
$\begingroup$
$\endgroup$
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.)