<p>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 following is asked:
&quot;...what you can do is to look at the proof of NP-hardness for CNF-SAT(and ultimately 3-SAT) and see if there might not be 2-SAT formulas come out in the reduction if you use the word problem translated for a <em>deterministic</em> Turing machine. When that is so (or you can easily convert the resulting formulas into 2-CNF), then it has been shown that 2-SAT is at least as difficult like the word problem for det. Polynomial Time Machines. So is then complete for class P.&quot;</p>
<p>I understand the proof for 3-sat to be np-hard but i don't get the idea that is described for 2-sat to be p-hard. Could anyone help me out understanding the way of thinking to proof that 2-sat is p-hard? also excuse my bad english</p>
<p>any help is appreciated, thanks in advance</p>

CC BY-SA 4.0
2022-05-14T13:00:01.317Z
Please post this question on https://cs.stackexchange.com, not here on cstheory. cstheory is for research-level questions.
Albert Hendriks
CC BY-SA 4.0
2022-05-14T13:48:59.390Z
I concur with the first comment. But anyway, 2-SAT is *not* P-hard (unless P = NL, that is): 2-SAT is actually NL-complete. You can find this in any number of sources, such as Wikipedia.
Emil Jeřábek
CC BY-SA 4.0
2022-05-16T21:19:37.037Z
Cross-posted: https://cs.stackexchange.com/q/151559/755, https://cstheory.stackexchange.com/q/51453/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<sat><p-hardness><2sat>
proof that 2-SAT is P-hard
hellothere
# proof that 2-SAT is P-hard

(Asked by: username_0 on 2022-05-14)

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 following is asked:
"...what you can do is to look at the proof of NP-hardness for CNF-SAT(and ultimately 3-SAT) and see if there might not be 2-SAT formulas come out in the reduction if you use the word problem translated for a *deterministic* Turing machine. When that is so (or you can easily convert the resulting formulas into 2-CNF), then it has been shown that 2-SAT is at least as difficult like the word problem for det. Polynomial Time Machines. So is then complete for class P."

I understand the proof for 3-sat to be np-hard but i don't get the idea that is described for 2-sat to be p-hard. Could anyone help me out understanding the way of thinking to proof that 2-sat is p-hard? also excuse my bad english

any help is appreciated, thanks in advance

**Tags:** sat, p-hardness, 2sat

> **Comments:**
> **username_1**: Please post this question on https://cs.stackexchange.com, not here on cstheory. cstheory is for research-level questions.  
> **username_2**: I concur with the first comment. But anyway, 2-SAT is *not* P-hard (unless P = NL, that is): 2-SAT is actually NL-complete. You can find this in any number of sources, such as Wikipedia.  
> **username_3**: Cross-posted: https://cs.stackexchange.com/q/151559/755, https://cstheory.stackexchange.com/q/51453/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 0 answers

