Proof that 2-sat is P-hard?

Question

i figured out this is what i want to know: in Cook's theorem it is shown that SAT is NP-hard. he shows it by showing that sat is at least as difficult like the word problem for nondet. Polynomial Time Machines. I want to know how i would proof that 2-sat is P-hard while showing that 2-sat is at least as difficult like the word problem for DET. Polynomial time machines

old question: 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

Answer 1

2SAT is NL-complete (with respect to logspace reductions). Wikipedia outlines a proof:

1. We start by describing Krom's algorithm for 2SAT, using the implication graph. In this directed graph, the vertices are all literals, and each clause $\ell_1 \lor \ell_2$ corresponds to a pair of edges $\bar{\ell}_1 \to \ell_2$ and $\bar{\ell}_2 \to \ell_1$ (possibly self-loops, if $\ell_1 = \ell_2$). If there is a directed path from $x$ to $\bar{x}$ and from $\bar{x}$ to $x$ for some variable $x$, then the formula is unsatisfiable. It turns out that if there is no such directed path, then the formula is satisfiable. Roughly speaking, for every variable $x$, either there is no path from $x$ to $\bar{x}$ or there is no path from $\bar{x}$ to $x$ (or both), and we set the value of $x$ accordingly. This process should be done iteratively.
2. Implement this algorithm in coNL. That is, given an unsatisfiable 2CNF, we should give a logspace algorithm that verifies that using advice. The advice consists of two directed paths in the implication graph, from some variable $x$ to its negation $\bar{x}$ and from $\bar{x}$ to $x$. This advice can be verified in logarithmic space.
3. The Immerman–Slezepcsényi theorem states that NL=coNL. Consequently, 2SAT is in NL.
4. To show that 2SAT is NL-hard, we reduce from directed reachability, a well-known NL-complete problem. Directed reachability is the following problem: given a directed graph $G$ and two vertices $x,y$, determine whether there is a directed path from $x$ to $y$ (the undirected version is L-complete due to Reingold's theorem). Given an instance $(G,x,y)$ of directed reachability, we construct an instance of 2SAT as follows. The variables are the vertices of $G$. For each edge $(u,v)$, there is a clause $\lnot u \lor v$. In addition, there are clauses $x$ and $\lnot y$. This instance is unsatisfiable iff $y$ is reachable from $x$. (This is actually a reduction from directed reachability to co2SAT, but since NL=coNL, this is OK.)

If an NL-complete problem is P-hard, then P collapses to NL, which is considered unlikely. Since 2SAT is NL-complete, this suggests that it is not P-hard.