2011-10-29
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?
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). <br><br>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?
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.
l1 OR l2
corresponds to the two edges
not l1 -> l2
and
not l2 -> l1
Recall also that (not l1 iff l1) is bad.
Here's a hint: You want to use PATH. Imagine a clause<br><br>l1 OR l2<br><br>corresponds to the two edges<br> not l1 -> l2<br>and<br> not l2 -> l1<br><br>Recall also that (not l1 iff l1) is bad.
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.
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.
'''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.<br><br>My question:<br><br><br>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?)<br><br>This question is represented on the input tape as where M is the machine that decides L, and the string in question, x.<br><br>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:<br><br> right?<br><br>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?<br><br>So yeah, I am wondering what is left on the work/output string after our computation of f on .<br><br><br>The professor's reply:<br><br><br>A logspace reduction from L to L' is a a function f such that<br>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<br>logspace, just that if we want to compute a bit of f we can compute that in logspace.<br>
(c) 2024 Yioop - PHP Search Engine