PHP Search Engine

HW3 Problem 4: Show 2SAT is in NL .

'''Originally Posted By: jnewth'''

It seems like we can proceed similar to the way we show a problem is in NP. We usually do this with the concept of a verifier, ie, if someone gives us a certificate that solves the 2SAT problem, can we verify in L space that this certificate is correct. Alternatively, we can demonstrate a transformation from an instance of the 2SAT problem to an instance of another NL problem (in L space, I think). I believe in class the professor suggested the latter approach, but in reading the above, I think that the first approach will be simpler. Does anyone have an insight?

'''Originally Posted By: jnewth''' It seems like we can proceed similar to the way we show a problem is in NP. We usually do this with the concept of a verifier, ie, if someone gives us a certificate that solves the 2SAT problem, can we verify in L space that this certificate is correct. Alternatively, we can demonstrate a transformation from an instance of the 2SAT problem to an instance of another NL problem (in L space, I think). I believe in class the professor suggested the latter approach, but in reading the above, I think that the first approach will be simpler. Does anyone have an insight?

-- HW3 Problem 4: Show 2SAT is in NL

Here's a hint: You want to use PATH. Imagine a clause l1 OR l2 corresponds to the two edges not l1 -&gt; l2 and not l2 -&gt; l1 Recall also that (not l1 iff l1) is bad.

Here's a hint: You want to use PATH. Imagine a clause l1 OR l2 corresponds to the two edges not l1 -> l2 and not l2 -> l1 Recall also that (not l1 iff l1) is bad.

-- HW3 Problem 4: Show 2SAT is in NL

'''Originally Posted By: jnewth'''

This is the transcript of an email exchange I had with the professor regarding logspace reductions in the context of problem 4 and the proof that PATH is NL-COMPLETE. My question: On page 89 the book shows that PATH is NL-COMPLETE by showing some other NL language reducing to it. Im curious as to what the &quot;output&quot; of such a reduction function is? For example, if I understand correctly, we are given a problem is x in L (our NL language?) This question is represented on the input tape as where M is the machine that decides L, and the string in question, x. Our function f is operating on M and x and writing something to its output, right? It's not actually solving the problem, or computing M on x, or anything like that, right? It's trying to come up with another string that looks like: right? But I keep thinking that a graph that represents the original problem is going to be big, much bigger than logspace. Is this not correct? So yeah, I am wondering what is left on the work/output string after our computation of f on . The professor's reply: A logspace reduction from L to L' is a a function f such that x in L iff f(x) in L' and such that the ith bit of f is computable in logspace. Notice we don't say that we can output the whole f in logspace, just that if we want to compute a bit of f we can compute that in logspace.

'''Originally Posted By: jnewth''' This is the transcript of an email exchange I had with the professor regarding logspace reductions in the context of problem 4 and the proof that PATH is NL-COMPLETE. My question: On page 89 the book shows that PATH is NL-COMPLETE by showing some other NL language reducing to it. Im curious as to what the "output" of such a reduction function is? For example, if I understand correctly, we are given a problem is x in L (our NL language?) This question is represented on the input tape as where M is the machine that decides L, and the string in question, x. Our function f is operating on M and x and writing something to its output, right? It's not actually solving the problem, or computing M on x, or anything like that, right? It's trying to come up with another string that looks like: right? But I keep thinking that a graph that represents the original problem is going to be big, much bigger than logspace. Is this not correct? So yeah, I am wondering what is left on the work/output string after our computation of f on . The professor's reply: A logspace reduction from L to L' is a a function f such that x in L iff f(x) in L' and such that the ith bit of f is computable in logspace. Notice we don't say that we can output the whole f in logspace, just that if we want to compute a bit of f we can compute that in logspace.