## 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.

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

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

4. 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

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

6. what is L?

7. L = LOGSPACE.

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

8. that is great source of ideas, really

9. Are you going to post the answer? =)

10. 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.

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

12. A is now P-complete by assumption

why are you allowed to make this claim?

13. 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

14. 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.