47 votes
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 ...
user avatar
36 votes
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 ...
user avatar
  • 141k
22 votes

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

The empty 3SAT instance (over no variables) has one solution.
user avatar
19 votes
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 ...
user avatar
  • 7,843
16 votes
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 7,843
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 $...
user avatar
  • 7,091
15 votes

Is generalized XOR-SAT efficiently solvable?

It looks like the Wikipedia article you linked to says that XORSAT (not just 3-XORSAT) is in P. The method by which they are solving that 3-XORSAT formula in their example very easily generalizes to ...
user avatar
15 votes

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

The reason you don't see things like approximation ratios in decision making problems is that they generally do not make sense in the context of the questions one typically asks about decision making ...
user avatar
  • 3,085
15 votes

Why is SAT so important in theoretical computer science?

It is worth mentioning that mathematicians cared about SAT [1] even before it was shown to be NP-complete. See for example Godel's 1956 letter to Von Neumann, where it is known that SAT is $\Omega(n)$ ...
user avatar
  • 288
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) \...
user avatar
14 votes
Accepted

Why do Shaefer's and Mahaney's Theorems not imply P = NP?

Schaefer's theorem applies only to a specific type of languages, those of the form $\mathrm{SAT}(S)$ for a finite set of relations over the Boolean domain or $\mathrm{CSP}(\Gamma)$ for a finite ...
user avatar
14 votes

Deterministic SAT solver

Core algorithms like DPLL and its refinements like CDCL are completely deterministic. Note that non-determinism doesn't necessarily mean that an algorithm may lead to a wrong result. For example we ...
user avatar
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 ...
user avatar
  • 34.1k
13 votes
Accepted

Is 2-SAT with XOR-relations NP-complete?

2-SAT-with-XOR-relations can be proven NP-complete by reduction from 3-SAT. Any 3-SAT clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT-with-XOR-relations expression $...
user avatar
  • 7,843
12 votes
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 ...
user avatar
  • 7,843
12 votes
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 ...
user avatar
  • 7,843
12 votes

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 ...
user avatar
12 votes
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 ...
user avatar
12 votes

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 ...
user avatar
11 votes
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 ...
user avatar
  • 7,843
11 votes
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 ...
user avatar
11 votes
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). ...
user avatar
  • 4,899
10 votes
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 ...
user avatar
  • 7,843
10 votes
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 ...
user avatar
10 votes

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,...
user avatar
10 votes

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 ...
user avatar
  • 393
10 votes

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

One variable: $(A \lor A \lor A)$
user avatar
  • 842
9 votes

Why do we care about random Boolean SAT formula?

If your solver is efficient for random 3-SAT, it by no means entails that it is efficient for an arbitrary 3-SAT instance. Randomly generated instances are very different from instances that arise in ...
user avatar
  • 22.1k
9 votes
Accepted

Lower Bounds for Size of Independent Set in a Graph?

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.
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible