Questions tagged [2sat]
The 2sat tag has no usage guidance.
5
questions
0
votes
0
answers
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[1]-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
- 557
1
vote
0
answers
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 ...
- 11
2
votes
2
answers
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
1
answer
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
0
answers
59
views
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 ...
- 916