# Tag Info

### Can anyone give me an instance of 3SAT with exactly one solution?

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

### 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

• 34.7k
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

### Can anyone give me an instance of 3SAT with exactly one solution?

One variable: $(A \lor A \lor A)$
• 842
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,...
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
Accepted

• 2,594
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

### 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
Accepted

• 80.4k