# Tag Info

Accepted

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

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

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

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

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

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

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

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

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

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