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



Browse other questions tagged or ask your own question.