Friday, July 16, 2010

How I Find Homework Problems

What do you get out of this paragraph (from Charlie Stross' The Atrocity Archives via Daniel Lemire)
The [Turing] theorem is a hack on discrete number theory that simultaneously disproves the Church-Turing hypothesis (wave if you understood that) and worse, permits NP-complete problems to be converted into P-complete ones. This has several consequences, starting with screwing over most cryptography algorithms—translation: all your bank account are belong to us—and ending with the ability to computationally generate a Dho-Nha geometry curve in real time.
I get a new homework question.
Show that NP-complete = P-complete if and only if NP = L.
Wave if you solve it.

14 comments:

  1. Where NP-completeness is w.r.t. polytime reductions and P-completeness is w.r.t. logspace reductions?

    ReplyDelete
  2. A pretty one: both directions require discovering something instructive (at least in my solution).

    ReplyDelete
  3. A New Kind of Grammars: A new kind of generative grammars that can produce the empty language is designed in this book.

    http://www.amazon.com/New-Kind-Grammars-generative-grammars/dp/1452828687

    ReplyDelete
  4. isn't that just another way of saying "show that for two computations that are in L, their composition is in L "?

    ReplyDelete
  5. L = LOGSPACE.

    The problem is a little more tricky than just composing logspace computations.

    ReplyDelete
  6. that is great source of ideas, really

    ReplyDelete
  7. Are you going to post the answer? =)

    ReplyDelete
  8. Here's the solution (SPOILER): Assume NP-complete = P-complete. SAT is now P-complete and thus in P so P=NP. Let A = {1}. Every language in NP poly-time reduces to A (since P=NP) so A is NP-complete. A is now P-complete by assumption so every language in P log-space reduces to A. Since A, like every finite language, is in log space we have L=P=NP.

    The other direction: If NP=L then every language A in NP (except Sigma^* and the empty set) is both NP-complete and P-complete so these are the same classes.

    This comment will be removed when I actually do give this problem for homework.

    ReplyDelete
  9. As I am taking your computational complexity class in the fall. I have written down the solution :)

    ReplyDelete
  10. A is now P-complete by assumption

    why are you allowed to make this claim?

    ReplyDelete
  11. Every language in NP poly-time reduces to A (since P=NP) so A is NP-complete.

    that doesn't make any sense to me

    ReplyDelete
  12. Consider the function f(phi)=1 if phi is SAT and f(phi)=0 if phi is not in SAT. If P=NP f is computable in poly-time and reduces SAT to A. So A is NP-complete by definition. The assumption is that every NP-complete set is also P-complete so A must be P-complete too.

    ReplyDelete