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.

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

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

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

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

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

ReplyDeletewhat is L?

ReplyDeleteL = LOGSPACE.

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

that is great source of ideas, really

ReplyDeleteAre you going to post the answer? =)

ReplyDeleteHere'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.

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

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

ReplyDelete

ReplyDeleteA is now P-complete by assumptionwhy are you allowed to make this claim?

ReplyDeleteEvery language in NP poly-time reduces to A (since P=NP) so A is NP-complete.that doesn't make any sense to me

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