[Computational Complexity] 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.
Posted By Lance to Computational Complexity at 7/16/2010 08:48:00 AM