0
$\begingroup$

I'm trying to prove that every language that is not the empty set or {0,1}* is complete for NL (nondeterministic logarithmic space) under polynomial-time Karp reductions.

I'm really not sure how to even approach this problem or what languages are being discussed if you exclude both the empty set and {0,1}*. Any suggestions to get me going in the right direction? Thanks!

Edit:

I feel like I may still be understanding the problem incorrectly. I seem to be finding that polynomial-time reductions can't be used to define NL completeness, but that's what I feel this question is asking. What am I thinking about wrongly here? Thanks.

$\endgroup$
  • 1
    $\begingroup$ Try the following hints: $NL\subseteq P$ and for every language $L$ that is not $\emptyset$ or $\{0,1\}^*$ it holds that there exist words $x\in L$ and $y\notin L$. $\endgroup$ – Shaull Nov 3 '13 at 18:04
  • $\begingroup$ @Shaull: Immediately your comment makes me realize I was looking at the language restriction completely wrong (I thought the problem was saying something different than it is). I'm guessing the rest of your hints will be very helpful as well. Thanks! $\endgroup$ – Jenny Shoars Nov 3 '13 at 18:15
  • $\begingroup$ I feel like I may still be understanding the problem incorrectly. I seem to be finding that polynomial-time reductions can't be used to define NL completeness, but that's what I feel this question is asking. What am I thinking about wrongly here? Thanks. $\endgroup$ – Jenny Shoars Nov 3 '13 at 18:54
  • 2
    $\begingroup$ You are exactly right. The question comes to show that if you use polynomial time reductions, then every language is NL-hard (by the way, it should say "hard", not "complete"). In my opinion, it is easier to show the same result for P, rather than NL (it still holds), since it is easier to imagine polynomial time, then nondeterministic logarithmic space. This of it this way - a Karp reduction can perform polynomial time computations within the reduction. Can you use this power? $\endgroup$ – Shaull Nov 3 '13 at 19:08

Your Answer

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

Browse other questions tagged or ask your own question.