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

[Computational Complexity] Maybe He Missed Some Math

Expand Messages
  • Lance
    Thomas Garrity s book All the Mathematics You Missed [But Need to Know for Graduate School] has a section on P versus NP which says The N in NP is somewhat of
    Message 1 of 1 , Feb 9, 2005
    • 0 Attachment

      Thomas Garrity's book All the Mathematics You Missed [But Need to Know for Graduate School] has a section on P versus NP which says

      The N in NP is somewhat of a joke; NP stands for "not polynomial".
      and later
      While initially the smart money was on P ≠ NP, today increasingly the belief is that the statement P=NP is independent of the other axioms of mathematics. Few believe P=NP.
      For the record NP stands for "Nondeterministic Polynomial-Time" (not a joke) and at least this complexity theorist feels that a proof of P≠NP exists and we just haven't found it yet. Just because we are too stupid to find the proof doesn't mean the problem is independent.

      I don't mean to be hard on Garrity. He should be lauded for including the P versus NP problem in his book.

      Thanks to Varsha Dani for the pointer.

      --
      Posted by Lance to Computational Complexity at 2/9/2005 04:40:58 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.