Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] How I Find Homework Problems

Expand Messages
  • Lance
    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
    Message 1 of 1 , Jul 16, 2010
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.