0
$\begingroup$

I know that 3SAT is in NP and 2SAT is in P. And 2SAT can reduce to 3SAT just says 3SAT is strictly harder than 2SAT, so I don't think this proves P = NP, but it doesn't seem to disprove it either.

$\endgroup$
  • 1
    $\begingroup$ $A \leq_{P} B$ means that problem $A$ can be reduced to $B$. You seem to have thought that it's the other way around? Also, "2SAT can reduce to 3SAT" only says that 3SAT is "not easier" than 2SAT. It doesn't imply "strictly harder". $\endgroup$ – CodeChef Apr 18 at 2:29
  • 1
    $\begingroup$ You are right, I just double checked the meaning of the sign. $\endgroup$ – ChaiTea Apr 18 at 3:38
0
$\begingroup$

2SAT can be solved in linear (!) time, so your reduction would certainly prove $P = NP$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ but 3sat can't be solved in linear time, it's NP. The reduction says 3sat is harder than 2sat, which is like saying NP is harder than P, but how does it prove NP = P ? $\endgroup$ – ChaiTea Apr 18 at 1:43
  • $\begingroup$ @ChaiTea But your question (or the title at least) is asking about $3SAT\le_p2SAT$. We trivially have $2SAT\le_p3SAT$, it's the other direction which would imply $P=NP$ if true. $\endgroup$ – Noah Schweber Apr 18 at 2:38
  • $\begingroup$ Okay I had the wrong understanding of the 3SAT ≤𝑃 2SAY. So this actually says 3SAT can be reduced to 2SAT, and if true, every instance of 3SAT can be turned into 2SAT and solved in P, and because we know 3SAT is NP, this implied P = NP ? $\endgroup$ – ChaiTea Apr 18 at 3:37
  • $\begingroup$ @ChaiTea is not because 3SAT is in NP, but because 3SAT is hard for NP (meaning that for any other problem A in NP, $A \leq_p 3SAT$) that we would conclude P = NP if it was true that $3SAT \leq_p 2SAT$. $\endgroup$ – Bernardo Subercaseaux May 18 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.