27 January 2009
Universality theory for cranks
From the geomblog, in 2004: a meta-proof of P=/!=NP. With very slight modifications this could be a meta-proof of the Riemann hypothesis, or any other outstanding open problem in mathematics, theoretical CS, theoretical physics, or other heavily mathematical fields. The cranks work in roughly the same way regardless of the specific question.
Subscribe to:
Post Comments (Atom)
3 comments:
The "meta-" part of the meta-proof is this: while it is evidently extremely difficult to obtain a proof of P != NP (or for that matter, of P = NP), it is in practice easy to check whether or not an alleged proof is correct. This is in reference to the formulation of P as the set of "easily" solvable decision problems, and NP as the set of decision problems which have easily *verifiable* solutions.
The labels of the interlocutors also reveal this subtext. The labels P, P' refer to "prover", and V, V', V'', etc to "verifier", which are the idiomatic participants in "interactive proof systems" --- a common setting for describing protocols for verifying solutions to problems in NP. In complexity, a "prover" is considered to be computationally unbounded but, despite the positive sounding name, untrustworthy. It is the job of the the polynomial-time bounded "verifier" to keep the "prover" honest.
The "meta-proof" reads like the script from a play from a skit meant to illustrate, if not *why* P != NP, at least some ironic anecdotal evidence for it.
I can't wait for my first opportunity to inform one of the smug CS grad students here that their algorithm has a glemish.
Approvingly your article helped me terribly much in my college assignment. Hats off to you post, choice look progressive in behalf of more interrelated articles soon as its one of my pick subject-matter to read.
Post a Comment