# Questions tagged [2-sat]

The tag has no usage guidance.

44 questions
Filter by
Sorted by
Tagged with
60 views

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

I am aware that 2SAT is polynomial while 3SAT is not, but I am looking for an intuition why its so. After all, even in 2SAT we can attempt all possible truth functions and its $2^n$. So I am hoping ...
34 views

### Is there a reduction from 2sat to bpm?

Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
17 views

118 views

565 views

### Is this possible to solve 4SAT in polynomial time? [closed]

I know and admit that this is long, but please read it slow and understand everything. I think that this is one of the most interesting questions asked in computer science ever. I don't expect for ...
754 views

### 2-SAT implication Understanding

Having a simple 2-SAT problem where the equation is simply: $a \lor b$ We have two implications: $\lnot a \Rightarrow b$ $\lnot b \Rightarrow a$ Thus, in the graph we build we add edges similar to ...
88 views

### 2-clause satisfiability associated graph

A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P: 2-SAT: Input : A conjunction $\Phi$...
259 views

### Is Max-2SAT with exactly 3 occurrences per variable APX-hard?

The Max-2SAT problem asks if at least k clauses of a 2CNF formula can be satisfied. The Max-2SAT(at-most-3) problem is the restriction in which every variable occurs in at most 3 clauses (counting ...
282 views

### Is SAT-Problem with XOR and AND NP-complete

Is this problem NP-complete? I have many restrictions like this and want to find a feasible solution: ((a and b) xor (c and d)) = 1 with a,b,c,d are arbitrary literals. It looks similar to XOR-2SAT ...
1k views

### How to do last step of Krom's algorithm for solving 2SAT problems

I was making a program for solving 2 SAT problems, using Krom's algorithm. I did not found a lot of information searching in Google, so I used Wikipedia's description of Krom's algorithm to implement ...
117 views

### How to check wether a 2SAT implication graph has a bad loop or not?

m doing a practise quiz which my professor has posted online, one of the questions im very confused about was this one. ...
737 views

### Can you solve 2-sat problem when truth assignments of some variables are determined

I am trying to find a assignment to satisfy a 2-sat statement. Problem is some of the clauses are 0 or x or 1 or x. I think the <...
203 views

### Schaefer's dichotomy theorem and reformulating 3-literal clauses

Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would ...