# 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 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

• Please post this question on cs.stackexchange.com, not here on cstheory. cstheory is for research-level questions. May 14 at 13:00
• 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. May 14 at 13:48
• – D.W.
May 16 at 21:19