# Tag Info

Accepted

### Why is SAT so important in theoretical computer science?

SAT was the first problem shown to be NP-complete, in Stephen Cook's seminal paper. Even nowadays, when introducing the theory of NP-completeness, the starting point is usually the NP-completeness of ...
Accepted

### Why there are no approximation algorithms for SAT and other decision problems?

Approximation algorithms are only for optimization problems, not for decision problems. Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to ...

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

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

### Is finding a solution of a satisfiability problem harder than deciding satisfiability?

As mentioned in a comment, any method of determining satisfiability of a Boolean formula can be easily converted into a method for finding the satisfying variable assignment. This is because Boolean ...
Accepted

### DNF to CNF conversion: Easy or Hard

If you are willing to introduce additional variables, you can convert from DNF to CNF form in polynomial time by using the Tseitin transform. The resulting CNF formula will be equisatisfiable with ...

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

Accepted

### What is wrong with this seeming contradiction with a paper about AND-compression of SAT?

The confusion arises from a misunderstanding of what being polynomial in the size of the largest instance means. It does not mean that polynomial growth of the compressor's output is allowed as the ...
Accepted

### If one shows that UNIQUE k-SAT is in P, does it imply P=NP?

This is still an open question; UP is not known to be equivalent to NP. In the paper "NP Might Not Be As Easy As Detecting Unique Solutions," Beigel, Burhman and Fortnow construct an oracle under ...

### Why does Schaefer's theorem not prove that P=NP?

Schaefer's theorem covers a very specific situation: you are given a finite set $\Gamma$ of relations, and are interested in the complexity of $\mathrm{CSP}(\Gamma)$. Schaefer's theorem gives you an ...
Accepted

### Why the need for TSP solvers when there are SAT solvers?

TL;DR: polynomial reduction increases the size of a problem; using a specific solver allows you to exploit the structure of a problem. When you reduce one NP-complete problem to another one, the size ...

### Why is SAT so important in theoretical computer science?

I'll add another perspective, based loosely on Andreas Blass's comment on the accepted answer: SAT is in some sense 'conceptually universal' for a broad class of NP-complete problems. To be more ...
Accepted

### Why don't modern SAT solvers use the notion of a "watched clause", in the same way they use the notion of a "watched literal"?

A typical SAT solver notices that a satisfying assignment has been found when there are no more variables to assign. So the only time that a SAT solver would save by early notification is the time it ...
Accepted

### Is weighted XOR-SAT NP-hard?

A classical result of Berlekamp, McEliece, and van Tilborg shows that the following problem, maximum likelihood decoding, is NP-complete: given a matrix $A$ and a vector $b$ over $\mathbb{F}_2$, and ...
Accepted

### Is "Reachable Object" really an NP-complete problem?

A problem $P$ is NP-complete if: $P$ is NP-hard and $P \in \textbf{NP}$. The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). ...
Accepted

### Recipe book for SAT encodings?

I read a survey paper a few years ago that seems relevant, "Successful SAT Encoding Techniques" by Magnus Björk. Abstract: This article identifies good practices for SAT encodings by ...
Accepted

### Why does Schaefer's theorem not prove that P=NP?

When you translate an arbitrary NP problem $L$ to CSP, you end up with some set of instances with some constraint language (set of relations) $\Gamma$. What Schaeffer's theorem says is that ...

### P=NP, isn't it?

Every CNF is falsifiable (choose a clause and choose a truth assignment which falsifies it). Unfortunately, the opposite of "CNF $\varphi$ is satisfiable" is not "CNF $\varphi$ is falsifiable". Rather,...

### Equisatisfiability in the reduction from 4-SAT to 3-SAT

You're right in saying that they should be equisatisfiable. And they are. I'm not sure why you think converting your unsatisfiable $4-\text{SAT}$ instance into a $3-\text{SAT}$ instance would make it ...

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

One variable: $(A \lor A \lor A)$
The relevant result is known as Turán's theorem. It states that if a graph has less than (roughly) $n(n-1)/(2r)$ edges then it has an independent set of size $r+1$, and this is tight.