- Sherlock Holmes doesn't know what the Mill. Prizes are. I thought most educated people did. Everyone I know knows about them. Could be the company I keep.
- The show indicates that `Solving P vs NP' means `showing P=NP' It never seems to dawn on them that maybe P is NOT NP.
- The show assumes that once P=NP is proven it will take a very short time to write a program to use it. If P=NP is true then I suspect taking the proof and making it work on real world problems would take several years.
- The show focuses on P=NP's implications for crypto. As Lance has pointed out in his book if P=NP then the benefits for society are GINORMOUS, and would dwarf the relatively minor problem of having to switch to private key (I agree with Lance for the long term, but I think the short term would be chaotic for security).
- The show refers to seven Mill problems. While this is technically correct they really should mention that one of them (Poincare's conj.) was already solved.
- They seem to think that algebraic geom would be used on P vs NP. If they were claiming it was being use to prove P NE NP then I would think of the Geometric Complexity Theory Program and be impressed. Since they were using it to work on P=NP I'm less impressed. If Alg Geom really is used to prove P=NP then I'll be impressed.
- How was the episode- I am a fan of the show in general, and this was a solid but not outstanding episode. I wonder if I knew less about P vs NP would I enjoy it more.
- They are talking about P vs NP on National TV! That's kind-of nice. Only danger is the overhype. If P NE NP is shown and this has no real world applications then the public may be confused. I suspect we won't have to worry about that for at least 300 years.
Monday, October 07, 2013
P vs NP is Elementary? No-- P vs NP is ON Elementary
As I am sure you all know, the TV show Elementary (Premise- Sherlock Homes in Modern Day NY. He emails and Texts! Watson is a female! and...) had an episode that involved P vs NP in a big way. I think they would have been better off with a fictional problem (Bourbaki's conjecture in Recursive Algebraic Topology?) rather than a real problem that they could say rather odd things about.
Subscribe to:
Post Comments (Atom)
I don't agree with 1. I am pretty sure that a (vast?) majority of educated people are not aware of the millenium prizes. The point is that many people may have heard about the prizes, but many of them have forgotten because they do not care at all!
ReplyDeletemore intro material/survey/links on P vs NP, see math monster
ReplyDeleteas for publicizing claymath prizes among the public & increasing visibility etc, it might have helped if Perelman had accepted & furthermore been willing to do some "publicity". many awards do have this as a condition... maybe thankfully others do not... as for this quip "I suspect we won't have to worry about that for at least 300 years." ... not sure what you meant by that. could be interpreted many ways. both P=NP and P!=NP have huge applications...
ReplyDeletePerlman turning DOWN the prize may have given it more publicity!
DeleteBut alas, still not known now. His 15 minutes of fame are up.
My prediction is that P NE NP will be proved in about 300 years.
Jon Katz says that IF ITS NOT SOLVED IN 300 YEARS, ITS NOT GOING TO BE SOLVED. He may be right.
3centuries, eh, one of the most pessimistic forecasts Ive heard.... heck might as well just believe its undecidable for nearly the same effect!
Deletewhich reminds me, perelman once said he declined the award because he didnt want to be viewed as "an animal in a zoo". by the way other examples of contests that require publicity by contestants as part of the prize: american idol & miss america =(
"Jon Katz says that IF ITS NOT SOLVED IN 300 YEARS, ITS NOT GOING TO BE SOLVED. He may be right."
DeleteI think that's too pessimistic. FLT was open for 358 years and I'd surmise that P vs NP is vastly more difficult as essentially you have to give some characterization of every possible polynomial time algorithm.
To paraphrase Mark Twain, any calm person can already see — by reading MathOverflow wiki-answers, for example — that already it is more difficult to read an algebraic geometry textbook than to write one. And by the same token, any person can see that 300 years from now it will be easier for a body to rederive the entire corpus of STEM literature, than to read that literature with understanding.
DeleteRe: Millennium questions (perhaps even 3 of them)
ReplyDeleteMight I humbly suggest that if the "Keepers of Rigor and Purity" might momentarily consider tweaking away a certain inconsistent " impurity by convention" lying at the center of the number line and thereby consider the identity elements as "neutrally prime" - then one could restore complete symmetry to arithmetic, both elementary and complex, and thus, perhaps somewhat elegantly, demonstrate that both Goldbach and Zeta are merely number-theoretic equivalents of Emily Noether's theorems regarding symmetry preservation and conservation laws? Isn't logical consistency itself, also a symmetric requirement demanding conservation? Goldbach is about maintaining a binary pairwise symmetry among the primes upon symmetry-breaking and scaling that is implicated in the primes' one-to-one correspondent justification as a Cantorian countably infinite set. Goldbach isn't about prime distribution per se, it is only about symmetric consistency in arithmetic. The primes' lop-sided randomization on either side of zero requires symmetric renormalization And Goldbach simply shows us how that is accomplished. And Zeta essentially accomplishes a similar feat in a higher plane.
In summary, if Goldbach isn't true, logical consistency in arithmetic fails miserably.
just sayin'
Final "secret" of Goldbach, Riemann, and Noether, "Gödel, Escher, and Bach"....(again taking metaphorical liberties) :
ReplyDeleteA TOE and a finalization of theoretical unification is dependent upon a lost human talent for sematic/syntactic symmetry preservation.
The modern commitment to a tunnel-visioned adherence to the linguistic formalizations of symbolic logic has entirely muddled the "scientific brain" into believing that it is possible to attain unification by dismissing the necessary symmetric unification of both formal and informal language required of the human brain in order to maintain consistency in the universe which generated that brain. Metaphorically simplified:
From the viewpoint of the Universe itself, it is the human brain that is somewhat artificially and incompletely intelligent.
End sermon...
What is Mathematics?
ReplyDeleteTo answer that question one merely has to extend Kronecker's observation just a tiny bit further (and 'bit' here, is intended as a pun, of course ):
The 'gods or God' created the identity elements - 0,1 - everything that lies beyond raw machine code is merely there to provide the security for redundant bilateral symmetry preservation while the human ape enjoys the self-induced illusions of broken symmetry.
Advanced Mathematics is simply an abstract playground of self-symmetric "consistency" developed by higher apes to provide the amusement of "rigorous exercise" for their even higher ape descendants .
And so...
Once you "figure out" the simplicity of Goldbach and Riemann - trivial mathematical statements of a simple binary symmetry conservation law explaining the human need for rigorous consistency - you may move on and realize that there exists a more elegant explanation for FLT and Poincare than the one's thus far extracted.
And perhaps then, the cranial light bulb will start blinking out some code for P not= NP (?)
The Universal Turing Test will only be fully completed when the Bio/Technic-Singularity decides to commit cyber-suicide.
just sayin'
...
end parables and disengage...
P vs.NP simply requires further reduction.
ReplyDeleteIsn't every verification merely an answer to a question?
Isn't every proof merely an answer to a question?
Is the former query somehow "deeper" than the latter?
or,
Is the latter query an "anti-reduction" of the former?
Isn't answer merely a contrapositive of query?
Isn't it all just blatantly symmetric and anti-symmetric?
An Oracle can only provide a contradiction, p and not-p, because the one who listens to the oracle is always left with the further question of:
"Can the oracle be trusted?"
And so the listener, must go on and test the oracle's statement further or simply accept the oracle as objective truth. The old "leap of faith" trick.
And that is how it all works.
just sayin'
True or False - The deepest questions in computation are all reducible to a 3-body problem. (?)
ReplyDeleteThought experiment:
A human observer called A is observing a human questioner called B as that questioner queries a Turing-esque search engine, which is running an algorithm designed by a human programmer called C. Programmer C has designed the algorithm according to some very specific axioms. The algorithm is stochastic in nature.
Questioner B attempts to enter a query into the search engine framed as specifically as possible according to axioms which may or not be exactly the same axioms as those the search engine's designer, Programmer C, utilized. Programmer C has taken this into consideration of course, and that is why the algorithm is statistically designed to deliver a ranked list of possible answers for C's query.
So the query is entered and the search engine delivers the list. The list is ordered under an assumption that, most likely, the questioner is using the same axioms, but just in case, the list delivers alternatives.
The list of alternatives may be very, very long or it may be reasonably short - it will all depend on certain factors of axiomatic equivalence. We will, however, assume the list finite for the purpose of sensibility within constraints of polynomial time.
Thusly, Questioner B must now make a selection or "choice" from amongst the list provided by the search engine whose algorithm was designed by Programmer C.
How does Questioner B decide, and what will determine his or her own satisfaction with that selection? It all goes back to the question of axiomatic equivalence, but now it not only depends upon axiomatic equivalence, it also depends on how Questioner B and Questioner C interpret those axioms! Axioms and algorithms and one-to-one ordered correspondence of axiom interpretation - these all go into the functions!
And finally, what of that seemingly neutral human Observer A mentioned at the onset of this thought experiment? Observer A is the Arbitrageur. Observer A is merely trying to decide if the whole process he or she is observing is sensibly consistent or not, and if the axioms being utilized are in full accordance with his/her own axioms and his or her own interpretation of those axioms. Observer A intends to base all of his or her own further investments upon this observation.
So the whole thing boils down to a pairwise correspondence of axiom and interpretation of axiom amongst three bodies - A, B, and C.
And the clincher is that the bodies do not necessarily have to be human and do not necessarily have to even be Turing-esque.
But if they ARE human, then a decision has to made, perhaps by a fourth body, whether or not human brains are Turing-esque and whether or not such a question, or questions, can even be answered within polynomial time.
Oy Vey!
The human brain is presumed to be a Turing device which can both formulate questions and formulate answers. One might then also realize that it requires algorithms for both sides of the question and answer process - algorithms for question or example formulation and algorithms for proofs or verifications.
ReplyDeletePart of the Turing test for intelligence might be waiting for a device to ask an original question - but what would be the basis for determining originality? Isn't the reason behind research citation simply due to the fact that originality is perhaps impossible to fully determine in polynomial time? Is the demand for research citation due to an NP problem? Should an author need to consider citations of perhaps, alien civilizations? If the human brain is truly a deterministic Turing machine, is it truly capable of formulating absolutely original questions and answers or can it only run previously determined simulation?
So one might then ask, could the question of P vs. NP even arise in a world where P = NP? Would the P vs. NP question be just a self-referential question in such a world where the question was already answered and the answer was already programmed into all existing Turing devices?
And SO - ON to your original question:
ReplyDeleteIs P vs. NP Elementary or is it Complex?
Do you REALLY want an answer to that?
Because if you do, you are going to first have to listen to an informal lecture that contains the secret of both the Goldbach Conjecture and the Riemann Zeta. Only by understanding Goldbach and Zeta thoroughly and completely will you understand that all of Rigor And Mathematical Purity rests upon one tiny little dirty secret of contradiction and ambiguity that is locked away by the "Keepers of Rigor and Purity" in that tiny little symbol for the square root of negative one. What both Goldbach and Riemann Zeta are trying desperately to tell you is that you can only attain unification and equilibrium of mathematical sensibility (i.e., rigorous consistency) by keeping your mental hindquarters seaedt on the "Fifty Yard-line of Logic - the one-half position shown in Zeta and the even result of two odd primes shown in Goldbach. The real part and the imaginary part. The falsely "logical part" of the reals and the truly "imaginary part" of the complex numbers, AND VICE VERSA. This is the dirty little secret that the Keepers steal away from you after your childhood arithmetic lessons, and lock away from you in that imaginary unit later on.
Goldbach and Riemann simply serve to inform you that it requires both order and disorder, in combinations under unity and combinations above unity, in order to fully realize and continuously maintain symmetry and consistency throughout the mathematical experience. The reward of understanding both Goldbach and Zeta is the suspension of ambiguity required for P vs. NP. It will force you to ask yourself in the Turing machine in your head could possibly even have evolved in a world where P = NP holds completely.
(Think about that for a second or two, because your brain, assuming that it is a brain, entirely depends on P not= NP and P = NP sharing a somewhat peaceful co-existence for at least one-half of your polynomial time.)
The Goldbach Conjecture, the Riemann Zeta Hypothesis, and the Problems of Computational Complexity are the simplest non-problems in all of Mathematics, and yet they sit silently laughing at y'all from their current hideout at the Clay Institute.
So if y'all truly want to understand it all, and you are ready to take a small journey into the forbidden zone of bilateral symmetry and mathematical consistency sitting at the junction of fifty percent orderable objective truth and fifty percent un-orderable subjective imagination, then get back to me and I will present the groundwork for 3 very simple proofs for 3 very simple problems.
All it really requires is coming to grips with the only two important numbers in machine code - those algebraic identities tied up into a paradoxical unity called bit and a paradoxical dis-unity called the imaginary unit. When the journey is complete, the real secrets of the Euler equivalence - the e to the eye pi plus one equals 0 - that the "Keepers" let you mess with for awhile in elementary analysis but never afford you the proper amount of polynomial time to understand, will become so clear to you that you will slap yourselves upside the head.
Think about the above and get back to me. Or, HOPEFULLY better still, this brief little cryptic discussion will have forced y'all into approaching those 3 little millennium problems in a different way so that you can handily prove them for yourselves without my need to guide you any further.
All that the proofs real require is the blend negative one half imagination plus positive one half "reality". (and vice versa)
Mathematics is the explanation of the human brain formulated by the human brain itself - it is the ultimate ironic joke of self-reference. It is a very easy joke to get, I can assure.
Verstehen?
end lecture ...
As for Point #1, the fact that Holmes is unaware of the Millennium Prize makes perfect sense considering the character's canon. In the very first book, Watson tells that Holmes proudly claims he has no knowledge of the fact (that most "educated" people knew that the time) that the Earth revolved around the Sun. It's that kind of brass, proud ignorance that Holmes is partially famous for. After Watson reveals this knowledge to him he even boasts that he will try his best to un-learn it, to save room for more practical knowledge.
ReplyDeleteOf course the Holmes in Elementary is slightly different than the Holmes in Doyle's canon, but really, if Holmes *did* know about the Prize that would probably be more out-of-character than if he didn't.
I don't agree. Yes, Holmes may have vast ignorance about all "irrelevant" topics. But he has a huge knowledge about anything that can be relevant for solving crimes. Be it forensic science, or be it just real-world facts that explain how people react. In the same way as Holmes should, as I understand him, know of all people that are of some importance in society, he would also know about all prices that involve a price money large enough to kill for.
DeleteP vs. NP proof:
ReplyDeleteLesson 1;
P vs. NP essential involves a multi-body issue. It examines the notion of a single proof versus a multiplicity of verification correspondent to a proof, and it considers the problem in a multi-dimensional dynamic with both spatial and temporal considerations.
Can you somewhat agree with that assessment so far?
Now consider it in somewhat Cantorian terms: one-to-one- versus one-to potentially infinite.
We ask can the one-to-potentially infinite, whose infinity can be examined for pairwise verification on an example by example basis, be reconciled with a singular one-to-one consideration. Essentially, this is the same "final puzzle" that plagues all disciplines - scientific, metaphysical, and theological.
The final question is reducible to a 3-body consideration.
Now for your first assignment, I what you to read Abbott's "Flatland" and ask yourself one simple question:
What is wrong with the Flatland analogy?
Here is a hint:
Intelligent consciousness requires, at minimum, 3 dimensions. You cannot use a 2 dimensional analogy toward a problem requiring intelligent consciousness and LOGIC.
Logic requires the ability to conceptualize beyond the next nearest point, as would happen in Flatland. Conscious intelligence with LOGIC and Scientific predictability could not occur in Flatland.
This, perhaps, will inspire some thoughtfulness for the student.
end lesson one...
"Can you somewhat agree with that assessment so far?"
DeleteI'm going to go with 'No'.
Amazing how quickly any post involving P =? NP attracts every random crackpot.
You can find here a very new statement on the PvNP Problem
ReplyDeletehttp://www.one-zero.eu/resources/PNP.pdf
or on facebook
https://www.facebook.com/suly.dof
"Simple proof that P is not equal to NP" www.youtube.com/watch?v=xCzwlrNQQGo
ReplyDeleteI'll reserve judgment on this one.
ReplyDelete