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 ...
John L.'s user avatar
  • 39k
9 votes
Accepted

Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

$u = (a \vee b) \iff (u \vee \bar{a}) \wedge (u \vee \bar{b}) \wedge (\bar{u} \vee a) \wedge (\bar{u} \vee b) =1 $ Unfortunately, the equivalence above does not hold. Let $a=\text{false}$, $b=\text{...
John L.'s user avatar
  • 39k
7 votes
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 ...
Yuval Filmus's user avatar
7 votes
Accepted

Expected length of a random walk on a line

The behavior when $p = 1/2$ and when $p > 1/2$ is rather different. When $p > 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. ...
Yuval Filmus's user avatar
5 votes
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 ...
raka's user avatar
  • 166
5 votes

2-SAT implication Understanding

You are asking why we can model the equation $a \lor b$ as two directed edges in a graph. The answer is that mathematics is a free country, and we are allowed to do whatever we want. The only ...
Yuval Filmus's user avatar
4 votes
Accepted

Is this case of weighted 2SAT NP-complete?

You can express the predicate "$x = y$" using one occurrence of each polarity: $$ (x \lor \lnot y) \land (\lnot x \lor y). $$ Consider now an instance of weighted 2SAT, in which each variable appears ...
Yuval Filmus's user avatar
4 votes
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 ...
Yuval Filmus's user avatar
4 votes
Accepted

Give an NL-algorithm for complement of 2-SAT

Question1: What is the difference between 2SAT and the complement of 2SAT? The set of all strings that do not describe satisfiable 2CNF formulas. Question2: It is known that NL is contained in P, ...
David Richerby's user avatar
4 votes

Is SAT-Problem with XOR and AND NP-complete

Your question is likely answered by Schaefer's dichotomy theorem. In particular, if an instance of your problem is a conjunction of formulas, each one depending on a bounded number of variables, then ...
Yuval Filmus's user avatar
4 votes
Accepted

Is 2-SAT over Linear Real Arithmetic in P or NP?

You can express the fact that a variable $x_i$ is Boolean as follows: $$ (0 \leq x_i \leq 1) \land ((x_i \leq 0) \lor (x_i \geq 1)). $$ You can express the condition $x_i \lor x_j \lor x_k$ as $$ x_i +...
Yuval Filmus's user avatar
4 votes

Proof that 2-sat is P-hard?

2SAT is NL-complete (with respect to logspace reductions). Wikipedia outlines a proof: We start by describing Krom's algorithm for 2SAT, using the implication graph. In this directed graph, the ...
Yuval Filmus's user avatar
3 votes
Accepted

Padding a 2SAT clause

Sometimes we insist that the three literals in a 3SAT clause belong to different variables. This ensures, for example, that a random assignment satisfies a clause with probability exactly $7/8$. The ...
Yuval Filmus's user avatar
3 votes
Accepted

MAX 2-SAT is polynomial time reducible to 2-SAT?

I think there is some confusion here. MAX-2-SAT is NP-Hard (and its decision version is NP-Complete), while 2-SAT is in P and hence also in NP. This means that 2-SAT is polynomial-time reducible to (...
Steven's user avatar
  • 29.4k
3 votes
Accepted

Counting models satisfying a boolean formula

For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with ...
David Richerby's user avatar
3 votes
Accepted

Is there an algorithm to find out if a truthtable can be represented as 2-sat, and if so find its 2-cnf?

This answer assumes that a 2CNF representation of a function is a 2CNF (on the same set of variables) that agrees with the function on all inputs. Let's say that a clause $C$ is consistent with a ...
Yuval Filmus's user avatar
3 votes

3-SAT with atmost 3 variables and variable occuring once per clause

Consider a bipartite graph $G=(C+V, E)$, where $C$ is the set of clauses and $V$ is the set of variables in the SAT instance. There is an edge $(c,x)$ with $c \in C$ and $x \in V$ if $x$ appears (...
Steven's user avatar
  • 29.4k
2 votes

How 2-QCNF algorithm works?

Aspvall, Plass and Tarjan describe a linear time algorithm determining the truth value of quantified 2CNFs in their paper A linear-time algorithm for testing the truth of certain quantified Boolean ...
Yuval Filmus's user avatar
2 votes
Accepted

Is this possible to solve 4SAT in polynomial time?

The problem is that when you split your clauses, you don't transform your $4SAT$ problem to a $2SAT$ problem. You still have an $NP$-complete problem to which an efficient $2SAT$-algorithm cannot be ...
Mike B.'s user avatar
  • 1,368
2 votes

2-SAT implication Understanding

The arrows symbolize material implication, which is the operator with the truth table $$\begin{matrix} A & B & A\Rightarrow B \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ ...
David Richerby's user avatar
2 votes
Accepted

2CNF with 3 variable occurences

The following is unsatisfiable: $$ (x \lor y) \land (x \lor \lnot y) \land (\lnot x \lor z) \land (\lnot z \lor w) \land (\lnot z \lor \lnot w) \land (y \lor w). $$ This contains every variable ...
Yuval Filmus's user avatar
2 votes

How Tarjan algorithm work for the 2-SAT

a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation. But I don't find any reason for the right to left direction. ...
Kyle Jones's user avatar
  • 8,091
2 votes

Give an NL-algorithm for complement of 2-SAT

Assuming that P≠NL, we know that P-complete problems are not in NL. The prototypical example is the Circuit Evaluation Problem, in which you are given a circuit (with constants as inputs), and the ...
Yuval Filmus's user avatar
2 votes

Doubt regarding the implications of a 2-SAT constraint

$A\rightarrow B$ doesn't necessarily mean that $B\rightarrow A$. In your example, "$x_1$ is false then $x_2$ must be true" doesn't imply that if $x_2$ is true, $x_1$ must be false. Therefore,...
nir shahar's user avatar
  • 11.5k
2 votes
Accepted

Showing resolution algorithm for 2SAT is polynomial time

In the case of 2SAT, resolving two clauses does not increase their width (the width of a clause is the number of literals appearing in it). This is not the case for 3SAT, where resolution could ...
Yuval Filmus's user avatar
2 votes

Why can $2$-SAT be solvable efficiently, but $3$-SAT not?

An algorithm running in time $2^n$ is extremely slow. Fortunately, there are better algorithms for solving 2SAT. Here is one such algorithm. Suppose that $C_1$ and $C_2$ are two clauses (disjunctions ...
Yuval Filmus's user avatar
2 votes
Accepted

Describe statement "Exactly k out of n variables should be true" in 2-SAT in time polynomial to n and k?

If $x,y,z$ are three satisfying assignments of a 2SAT formula $\phi$, then the bitwise majority of $x,y,z$ is also a satisfying assignment $\phi$. To verify this, it suffices to check that this works ...
Yuval Filmus's user avatar
2 votes

Why do the 2-SAT techniques do not work for 3-SAT?

The issue might be that 2SAT can be solved in polynomial time while 3SAT is NP-complete and can't. When the computational complexity becomes much higher, the proofs of your 2SAT method might not ...
Würthi's user avatar
  • 151
2 votes
Accepted

Complexity of this variant of $⊕2SAT$?

This problem can be solved easily: trivially, the number of solutions is 0, so the parity is even. Consider any other variable $b$. Then because the formula $\varphi$ must contain all clauses that ...
D.W.'s user avatar
  • 159k

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