1
$\begingroup$

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.
$\endgroup$
6
  • $\begingroup$ What kind of reduction are you considering? Polynomial many-one? Logspace many-one? Turing reduction? $\endgroup$
    – Nathaniel
    May 14 at 14:16
  • $\begingroup$ @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 $\endgroup$
    – heythere
    May 14 at 14:24
  • $\begingroup$ @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. $\endgroup$
    – heythere
    May 14 at 14:34
  • $\begingroup$ @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 $\endgroup$
    – heythere
    May 14 at 14:55
  • $\begingroup$ Also, what is the word problem for DET? $\endgroup$ May 14 at 15:30

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

heythere is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.