# 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 ...
• 8,091

• 39k
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. ...
• 277k

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

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

• 4,817

### 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, ...
• 277k
Accepted

### Why is 3-SAT used for proving NP-Completeness so often?

You can indeed use any known NP-Hard problem as a candidate for your reduction. In my opinion, it has more to do with the fact that 3-SAT (a variant of SAT) was originally proven to be NP-Hard (see ...
• 565
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 ...
• 277k

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

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

### 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 ...
• 159k
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 ...
• 742

### 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 ...
• 277k

### How hard is random SAT?

Theoretically, we don't know how hard k-SAT is; P ?= NP remains an open question. Empirically, random $k$-SAT at the critical clause/variable ratio for each $k$ seems to require exponentially more ...
• 8,091
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

### How to choose between UC and PL when using the DPLL algorithm?

If you use the original specification of the DPLL algorithm, in which the unit rule is applied to a fixed point and then the pure literal rule, then only the unit rule is needed to reach a satisfying ...
• 8,091
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.6k
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 ...
• 81.7k
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,837

### 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. ...
• 159k
Accepted

### General structure of solutions to 3-SAT circuits

The theory you are after is universal algebra. See the excellent expository article of Hubie Chen, A rendezvous of logic, complexity, and algebra, which contains a streamlined proof of Schaefer’s ...
• 277k
Accepted

### Is every X3SAT instance with no cycles satisfiable?

The graph below is a positive answer without words. Here is the detailed proof. Definitions Let $X$ be an instance of X3SAT. $X$ is linear if any two clause shares at most one variable. $X$ is ...
• 39k
Accepted

### Time complexities of state-of-the-art SAT solvers with respect to length of the formula

For 3SAT, the number of variables is polynomially related to the number of clauses. (See the end for the justification.) Consequently, any algorithm for 3SAT whose running time is polynomial in the ...
• 159k
No. This problem is equivalent to XOR-3SAT, in which we interpret each clause as $x \oplus y \oplus z$, where $\oplus$ is the XOR operator, and ask whether it's possible to find values for all ...