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 :)
ReplyDeleteA is now P-complete by assumption
ReplyDeletewhy are you allowed to make this claim?
Every language in NP poly-time reduces to A (since P=NP) so A is NP-complete.
ReplyDeletethat 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