hi all, I heard about the infamous P=?NP problem in college and immediately was quite fascinated with it and made various attempts to work on it. its a very elegant problem, arguably one of the most elegant in existence.
the basic question is, is the set of languages that can be recognized by turing machines in polynomial time the same as the set that can be recognized in nondeterministic polynomial time? now, that sounds very technical, lets look at it simply. NP is a very nice shorthand for computer problems that can be solved efficiently with parallelism, ie, roughly, by "adding more cpus". P is the set of problems that can be solved efficiently on a nonparallel, "serial" computer. now, it seems that parallelism adds computational capability, but how much?
recently an HP PhD proposed a proof. this is one of the few serious attempts in recent times. there are many crackpot attempts.
already his proof has been largely discredited, but it was fun while it lasted. below Ive included some links on the subj, hope you enjoy reading a few.
years ago I told a gf that I wanted to be the "einstein of computer science" and solve this problem. back when I was young and naive. after many yrs of poking and prodding on it [now slightly over 2 decades for me], one comes to the natural conclusion that this is truly is the Mt Everest of computer problems.
there is a $1M award for the solution from the Clay mathematics institute. and again, after awhile, you begin to think that the hourly wage for the solution, if it actually exists, would turn out not to be a very high rate.
another idea occurred to me, to try to get a team of ppl together to work on the problem. many CS researchers work on it informally. but even though there is a massive award for the problem and its considered extremely significant, even fundamental, there is no significant funding for working on such a problem. some NSF grants could be considered to be tangential, but NSF is not going to fund an application, "our attack on a P=?NP proof". it would be considered crackpot of course.
after many years of looking into it I believe that P=?NP is a problem related to the thermodynamics of computation. just as there are laws in the universe that reveal that energy can be exchanged into different forms but always with a loss of efficiency, ie the presence of friction or energy losses, there is no "free lunch" as far as solving certain computer problems. ie they require a minimum amount of work no matter how efficient the computation or ingenious the algorithm.
ie there is a minimum complexity that cannot be overcome with any algorithm, no matter how efficient. different algorithms have more or less efficiency, but there is no perfect algorithm that has so little friction that one can defy the laws of physics with computation. which is interesting again, because it appears that at the heart of it, physics is about information manipulation. the researchers in QM and particle physics are likewise coming to that conclusion these days.
so P=?NP may be a fundamental theorem of information physics/thermodynamics. but we will be lucky to see a solution in our lifetimes. it may be even harder than some of the hardest problems in CS such as developing artificial intelligence. if you poll some CS scientists, they may actually agree that it might be easier to invent a thinking computer than find the solution to P=?NP.
maybe one of the best comparisons is to the Riemann conjecture which is now over 150 years old. P=?NP is much more modern and technological, having been asked first in 1970 by cook. only 40 years old this year, a mere youngster in comparison to some of the deep problems. actually some of the oldest unsolved theoretical problems go back to the greeks, at 2 millenia old, such as asking the existence of infinite twin primes, or odd perfect numbers.
mathematics itself is all about technology ie a kind of theoretical and symbolic technology. sometimes there are massive spinoffs, ie if you could solve those old greek questions, it might give you phenomenal theoretical power. or, it could be a dead end that illuminates only those somewhat, on some levels, meaningless and useless problems.
below I especially like the NYT article which emphasizes the cyberspatial collaborative aspects of working on the problem.
Computer science breakthrough: The end of P = NP? | Code analysis - InfoWorld
http://www.infoworld.com/t/code-analysis/computer-science-breakthrough-the-end-p-np-583
BBC News - Million dollar maths puzzle sparks row
http://www.bbc.co.uk/news/science-environment-10938302
HP boffin claims million-dollar maths prize • The Register
http://www.theregister.co.uk/2010/08/11/the_p_versus_np_problem/
New proof unlocks answer to the P versus NP problem—maybe
http://arstechnica.com/science/news/2010/08/new-proof-unlocks-answer-to-the-p-versus-np-problemmaybe.ars
Debate Over P vs. NP Proof Highlights Web Collaboration - NYTimes.com
http://www.nytimes.com/2010/08/17/science/17proof.html?hp
Technology Review: What Does 'P vs. NP' Mean for the Rest of Us?
http://www.technologyreview.com/computing/26086/?a=f
The status of the P versus NP problem by Lance Fortnow
http://portal.acm.org/citation.cfm?id=1562186
Crowdsourcing peer review
A claimed proof that P!=NP spurs a massive collaborative research effort
http://www.sciencenews.org/index/generic/activity/view/id/63252/title/Crowdsourcing_peer_review
TIP:
Enter the amount, and click "Tip" to submit!
Juliet Waters
the traveler
Nocheapshots
Darla Carmichael
Jeanine T. Abraham
Zaki Hasan
Salon.com
Comments
a) computation itself. this involves decidable vs undecidable problems. whether physics or the future of the universe, the progression of the universe is decidable is a deep question. a name that comes up here is Penrose who wrote a great book on the subj, "emperors new mind"
b) language complexity. this is P vs NP etc. all problems in decidable languages are definitely *computable* by definition. there do exist undecidable languages, eg the halting problem "language".
when you say computing the future of the universe in P, that statement makes no sense on the face of it. P and NP and other language classes fundamentally involve questions about "time" and "space" but not in the strictly physical sense, but in the sense of "how much computing resources are necessary, cpu time and memory 'space'".
a) there is a minimum amount of work/energy required to solve a particular computational problem.
b) algorithms solve problems with varying efficiency. the same problem can have algorithms that run in different times/space with the same results. therefore it seems reasonable to talk about "friction" which is the energy loss involved in somewhat redundantly solving a problem compared to the "perfect" algorithm. by "redundantly" I just mean that an algorithm took more time/space than it needed to.
c) increase of entropy in the universe over time. there does not seem to be a CS analog here. however I do believe that there are some strong analogies of entropy in physics to "disorder" or "randomness" in CS.
loosely speaking this is correct but there are great technical subtleties masked by the informal terminology, it takes a lot of analysis to nail down. complexity theory *is* the mathematics of computation.... in some ways approaching the level of complexity of other subjs eg calculus, and in some ways exceeding it....
yes an old neurobiology professor told me the same thing about the human brain. that the civilization uses the most sophisticated analogy it can find. in the other case, for the brain. 1st it was like fluid mechanics [davinci].. then like swiss clockwork. then like a telephone switchboard or communication network. then like a computer. next, like the Cloud [distributed computing etc]. there is some validity and some invalidity to this. its perfectly rational for us to attempt to describe something larger than us and our perspectives using analogies. and I would say there is some validity in *all* these analogies. we are getting close to the truth by convergence of analogies so to speak. but yes, there will be new analogies based on our new awarrenesses and models. the newer analogies do not discredit the prior ones, they elaborate on them. its an evolution of memes.