Questions tagged [2sat]
The 2sat tag has no usage guidance.
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'$ ...
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 ...
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 ...
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 ...
Find all paths between specially paired nodes in a DAG in linear time
If I have a DAG with 2n nodes partitioned into n pairs of nodes with e edges, is there a ...