# Questions tagged [2sat]

The tag has no usage guidance.

5 questions
Filter by
Sorted by
Tagged with
110 views

### Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

In parameterized complexity, for each fixed $q$, the problem Weighted $q$-CNF SAT is W-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
• 557
1 vote
211 views

### proof that 2-SAT is P-hard [closed]

i'm doing university work about the 2-sat problem and it is asked why 2-sat is p-hard. We discussed that 3-sat is np-hard and proved this by reduction from cnf-sat to 3cnf-sat. for my work the ...
206 views

### Separating 2-SAT from Clique

Since the P vs. NP problem is still an open problem, 2-SAT and Clique might both be in P if P = NP. Is there any known complexity measure whatsoever that is already mathematically proven to ...
• 414
1 vote
118 views

### Common solutions to 3SAT and 2SAT models comprised of the same variables

I have a problem which is a combination of 3SAT & 2SAT instances. Consider $L$ is a set of variables $(x_1 ... x_n)$. $S_3(L)$ is a 3-SAT instance and $S_2(L)$ is a 2SAT instance, both made of ...
• 41
1 vote