Questions tagged [2sat]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
68 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'$ ...
user avatar
1 vote
0 answers
121 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 ...
user avatar
2 votes
2 answers
184 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 ...
user avatar
  • 414
1 vote
1 answer
105 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 ...
user avatar
  • 41
1 vote
0 answers
45 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 ...
user avatar
  • 916