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

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

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

### Is SAT an existential question?

The SAT problem is a decision problem. It means that an algorithm that solves SAT must answer true or false, and not necessarily ...
• 15.8k

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

• 39.1k
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 ...
• 932

### 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 ...
• 2,529

### Is SAT an existential question?

If you have variables x1 to xn, and you decide in polynomial time whether the problem can be satisfied or not, then if it can be satisfied, you set x1 = true and check if it can still be satisfied. If ...
• 30.5k
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). ...
• 5,027

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

One variable: $(A \lor A \lor A)$
• 881

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

### 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 ...
• 413
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,101
Accepted

### Can we have a poly time reduction from 2-SAT to 2-Coloring problem?

As rotia mentions in their comment, to make the question meaningful we must restrict the power of the allowable reductions. The two most obvious choices are to allow only logspace reductions or only ...
• 278k
Accepted

### To prove 4-SAT CNF is NP-complete

In order to prove that 4-SAT is NP-complete, you need to prove that it is in NP and that it is NP-hard. Prove 4-SAT $\in$ NP Given an instance of 4-SAT and an answer that evaluates to TRUE, it's ...
• 246

### In SAT, do we require an assignment for arbitrary variables?

If the truth value of a formula is determined by setting only a subset of the variables, an author might skip describing the remaining truth values. However, by definition, a truth assignment gives a ...
• 22.6k
Accepted

### MAXSAT approximation

I won't speculate about your teacher's reasons for including the random assignment algorithm over yours. However, one advantage of random assignment is that, if every clause has at least $k$ literals, ...
• 81.9k
Accepted

### SAT algorithm for determining if a graph is disjoint

Given a graph $G = (V,E)$, here is a SAT instance which is satisfiable iff the graph is not connected. Pick an arbitrary vertex $v_0 \in V$, and add the following clauses, over the variables $x_v$ ...
• 278k
Accepted

• 3,724
Accepted

### Is #HORNSAT polynomial?

Even if decision is easy, the counting problem #HORNSAT is #P-complete [1], the counting analog of NP-completeness problem. Thus it is very unlikely it has a polynomial time algorithm (for example, if ...
• 956
Accepted

### Even, Itai & Shamir's limited backtracking algorithm for 2-SAT: is it really linear?

Below you can find a (non-optimized) python implementation of the algorithm. First, I give some hints explaining why this implementation runs in linear time. These hints assume that you know what is ...
• 278k