# Proof that 2-sat is P-hard?

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

New contributor
heythere is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• What kind of reduction are you considering? Polynomial many-one? Logspace many-one? Turing reduction? May 14 at 14:16
• @Nathaniel 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 May 14 at 14:24
• @YuvalFilmus i know that 2-sat is in P. so there should be a deterministic turing machine which solves the problem in polynomial time. so if there is b in P there should be a way to poly reduce b to 2-sat and i am looking for that. May 14 at 14:34
• @YuvalFilmus ok lets rephrase my question. how can i translate a deterministic turing machine into a formlar like in cook's theorem where he translates a NONdet. turing machine into a formular May 14 at 14:55
• Also, what is the word problem for DET? May 14 at 15:30

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.
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.)