22
votes
Can anyone give me an instance of 3SAT with exactly one solution?
The empty 3SAT instance (over no variables) has one solution.
- 221
16
votes
What is wrong with this simple proof of P=NP?
The monotone version of X3SAT that your proof is based on has the nice property that setting a literal false in one clause will never cause the negation of that literal to be true in another, which ...
- 7,853
16
votes
Can anyone give me an instance of 3SAT with exactly one 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 $...
- 7,193
15
votes
Accepted
Can anyone give me an instance of 3SAT with exactly one solution?
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)
\...
- 270k
14
votes
Accepted
Is a "local" version of 3-SAT NP-hard?
$(3,k)\text{-LSAT}$ is in P for all $k$. As you have indicated, locality is a big obstruction to NP-completeness.
Here is a polynomial algorithm.
Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c_1\wedge ...
- 34.7k
12
votes
Accepted
Reduction 3SAT and CLIQUE
Here is one possible way to reduce Clique to SAT (you can then further reduce it to 3SAT). This type of reduction is often used in (propositional) proof complexity, an area of complexity theory.
...
- 270k
10
votes
Can anyone give me an instance of 3SAT with exactly one solution?
One variable: $(A \lor A \lor A)$
- 842
9
votes
Accepted
3-SAT for variables appearing 3 times
There is no conflict between your references. The problem is that they have slightly different definitions of what 3-SAT is. You need to read the (original) theorems by Tovey very carefully.
Let r,...
9
votes
Accepted
Random restarts for unsatisfiable instances
There is some research in this area. In The Effect of Restarts on the Efficiency of Clause Learning Jinbo Huang shows empirically that restarts improve a solver's performance over suites of both ...
- 7,853
8
votes
Accepted
How to show ExactOneSAT is NP-Complete?
We can reduce 3SAT to ExactOneSAT (3SAT $\leq_P$ ExactOneSAT) as follows. Replace each clause $C_m$ by $(z_{m,1} \lor z_{m,2} \lor z_{m,3})$ and ensure that if $C_m$ is, say, $(v_i \lor \overline{v_j} ...
- 4,747
8
votes
Results on the difficulty of specific random 3-SAT problems?
Research has concentrated not on the number of satisfying assignments, but on the clause density $\alpha$. It is (more or less) known that:
Below a certain threshold, the problem is easy. Moreover, ...
- 270k
7
votes
The relation between 2SAT and 3SAT
Another way to put it:
2-SAT is in P and in NP.
if any problem in P (or in NP) is not NP complete, then P!=NP.
so if 2-SAT is not NP-complete, then P!=NP.
if P!=NP, then NP-complete problems are not ...
- 2,385
7
votes
Accepted
The relation between 2SAT and 3SAT
This is (sort of) a trick question. This is not about a connection between 2SAT and 3SAT, it is that if 3SAT is in P, then anything which is in NP and has at least one true instance and one false ...
- 196
7
votes
Accepted
Randomized algorithm for 3SAT
The random assignment algorithm can be derandomized (made deterministic) using the method of conditional expectations.
Let the 3SAT instance consist of clauses $C_1,\ldots,C_m$. During the algorithm ...
- 270k
6
votes
Expressing 3-SAT in first-order logic
There has been a lot of work on formalizing mathematics, and in all of this work one needs to express definitions, theorems and proofs within the logic that one is using for formalization.
This is ...
- 2,446
6
votes
How to use an algorithm to find a satisfying assignment in polynomial time?
The algorithm that decides 3-SAT just answers yes or no, satisfiable or not. It doesn't (directly) give you an assignment for the variables. You have to use the decision algorithm as a black box to ...
- 5,910
6
votes
Accepted
Do polynomial reduction functions work both ways?
The statement
Formula $F$ is satisfiable $\iff$ graph has an independent set
is imprecise, since it does not specify which graph we are taling about. Correcting this, we get:
There is a ...
- 14.2k
6
votes
Is integer factorization reducible to subset sum?
Yes, such a reduction exists. Subset Sum is NP-complete. FACT is in NP. Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum.
To find such a reduction ...
D.W.♦
- 143k
5
votes
Accepted
How must Grovers algorithm be modified in order to solve 3-SAT?
Grover's algorithm is already suitable. It promises that if there is at least one match, then it will output at least one match. It doesn't promise to output all matches, but you don't need all ...
D.W.♦
- 143k
5
votes
NOT satisfiable 3SAT instance certificate
A CNF which is not satisfiable is usually called unsatisfiable. A CNF which is unsatisfiable but becomes satisfiable if we drop any clause is minimally unsatisfiable.
Papadimitrious and Wolfe ...
- 270k
5
votes
Accepted
Why can $2$-SAT be solvable efficiently, but $3$-SAT not?
As was mentioned in a comment we can only say that 3SAT is NP-hard. In 2SAT you can take a variable $x$ and set it to true (or false). Then you can throw out any clauses where $x$ appears, or if a ...
- 166
4
votes
Accepted
3/2 - Approximation probabilistic algorithm for MAX-3-COLOR
If you simply uniformly at random (i.i.d) color each of the vertices of $V$ by each of the three possible colors, then for every edge $e\in E$, it's endpoint will be colored by different colors w.p. $\...
- 2,594
4
votes
Accepted
Hardness of 3SAT-k
The paper "A Simplified NP-Complete Satisfibility Problem" given as a reference in the scribe note has actually answered your questions.
Theorem 2.4: Every instance of $r,r$-SAT is satisfiable.
...
- 9,219
4
votes
How must Grovers algorithm be modified in order to solve 3-SAT?
Notwithstanding D.W.'s answer, the other option, if all you knew about Grover's algorithm is that it requires unique solutions, is to use the work of Valiant and Vazirani. Without getting into details,...
- 270k
4
votes
Accepted
If P != NP, then 3-SAT is not in P
The opposite is valid.
$3SAT$ is an $NP$-complete problem, so every problem in $NP$ can be reduced to $3SAT$.
If $P \neq NP$ and $3SAT \in P$, every problem in $NP$ would be in $P$, contradicting $P ...
- 1,348
4
votes
Accepted
Prove "almost clique" is NP complete
You can reduce to this from $CLIQUE$.
Given a graph $G=(V,E)$ and $t$, construct a new graph $G^*$ by adding two new vertices $\{v_{n+1},v_{n
+2}\}$ and connecting them with all of $G$'s vertices but ...
- 712
4
votes
monotone min-3-sat polynomial algorithm?
3SAT is NP-complete. Positive 3SAT (where all literals are positive) is in P, and thus presumably not NP-complete. There is an even simpler algorithm for Positive 3SAT: set all variables to true. ...
D.W.♦
- 143k
4
votes
Accepted
Why does the reduction from 3SAT to IS work?
The $\Rightarrow$ implication means that you need to prove that if the given $3SAT$ formula is satisfiable then there is a maximum IS.
So assume that the formula is satisfiable.
Since the formula ...
- 9,632
4
votes
Accepted
3-SAT with 3 variable occurences
Your second step isn't sound.
Take any unsatisfiable $3$-SAT formula (without restriction on the number of variable appearances) and perform the standard reduction to a formula where each variable ...
- 80.4k
4
votes
Accepted
How does the number of clauses affect the difficulty of a 3-SAT problem?
In general, there is no connection. An instance with a "small" number (say a few thousands) of clauses can be very difficult to solve in practice, while an instance with a "large" number (say several ...
- 22.1k
Only top scored, non community-wiki answers of a minimum length are eligible