patternModerate
Can anyone give me an instance of 3SAT with exactly one solution?
Viewed 0 times
anyonecanwithgive3satinstanceonesolutionexactly
Problem
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#135632, answer score: 17
Revisions (0)
No revisions yet.