Doubts continue on claim to have solved P vs NP mathematical question

Aug 17, 2010 by Lin Edwards weblog

One of the most complex mathematical problems in the world is proving either that P ≠ NP or P=NP, a riddle that was first formulated in 1971 by mathematicians Leonid Levin and Stephen Cook. The question was one of seven millennium problems set by the Clay Mathematical Institute (CMI) in Cambridge, Massachusetts as being among the most difficult to solve.

Vinay Deolalikar, a computer scientist from Hewlett-Packard's research arm based in Palo Alto, California, claims to have solved the problem and stands to win $1 million if his proof is accepted.

P refers to problems with solutions that are easy to find, in other words P is a class of problems for which an answer can be found in polynomial time. NP refers to problems with solutions that are almost impossible to find, but easy to verify, or in other words a class of problems for which an answer can be verified in polynomial time.

The Clay Mathematical Institute offers the following problem to illustrate NP: you have a list of 400 university students to be accommodated but there is only room in the dormitory for 100 students. The Dean has provided a list of pairs of incompatible students who cannot be on the final list. This is an NP-problem because it is extremely difficult to go through all possible combinations to come up with a list, but very easy to verify once a list is obtained. According to CMI the number of possible combinations is greater than the number of atoms in the universe.

If P ≠ NP some complex problems, such as the one above, could never be solved efficiently and there are serious limits on what computers will be able to accomplish in the future, whereas if P = NP every such problem would have a polynomial time solution. Mr Deolalikar writes that this would have profound implications for applications such as cryptography and on the question of whether or not human creativity could be automated.

Among those skeptical of Deolalikar's claim is Scott Aaronson, assistant professor of electrical engineering and computer science at the Massachusetts Institute of Technology (MIT), who said on his blog that he will personally add $200,000 to the prize, even though he can ill afford it, and he has not read Deolalikar's entire paper. He said if the proof was correct it would change his life so dramatically that "having to pay $200,000 will be the least of it." He later also gave his reasons for being so confident in MIT's technology review.

Another skeptic is Professor Richard Lipton at Georgia Tech College of Computing, who has been working on the P vs NP problem for three decades.

Deolalikar's paper is available online, and is being peer-reviewed by computer scientists. To be considered for the million dollar prize the paper must be published in an approved mathematics publication and must also retain general acceptance by mathematicians two years after the proof is published.

Explore further: Researchers help Boston Marathon organizers plan for 2014 race

More information: www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

Related Stories

What computer science can teach economics

Nov 09, 2009

(PhysOrg.com) -- Computer scientists have spent decades developing techniques for answering a single question: How long does a given calculation take to perform? Constantinos Daskalakis, an assistant professor ...

Getting a grip on school timetables

Jan 06, 2010

A new approach to solving the problem of school timetabling, known as a GRASP, has been developing by researchers in Brazil. They report details in a forthcoming issue of the International Journal of Operational Research.

Non-polypoid colon lesions associated with colorectal cancer

Mar 04, 2008

Flat, non-polypoid colorectal neoplasms (NP-CRNs), which may be difficult to detect, appear to be relatively common and may have a greater association with cancer compared with the more routinely diagnosed type of colorectal ...

Diesel exhaust exposure biomarker found

Jul 31, 2007

A Japanese-U.S. science team has created the first test to detect a biomarker for human exposure to diesel exhaust, a probable human carcinogen.

Recommended for you

Newlyweds, be careful what you wish for

16 hours ago

A statistical analysis of the gift "fulfillments" at several hundred online wedding gift registries suggests that wedding guests are caught between a rock and a hard place when it comes to buying an appropriate gift for the ...

Can new understanding avert tragedy?

18 hours ago

As a boy growing up in Syracuse, NY, Sol Hsiang ran an experiment for a school project testing whether plants grow better sprinkled with water vs orange juice. Today, 20 years later, he applies complex statistical ...

Crowd-sourcing Britain's Bronze Age

19 hours ago

A new joint project by the British Museum and the UCL Institute of Archaeology is seeking online contributions from members of the public to enhance a major British Bronze Age archive and artefact collection.

Roman dig 'transforms understanding' of ancient port

19 hours ago

(Phys.org) —Researchers from the universities of Cambridge and Southampton have discovered a new section of the boundary wall of the ancient Roman port of Ostia, proving the city was much larger than previously ...

User comments : 23

Adjust slider to filter visible comments by rank

Display comments: newest first

plasticpower
not rated yet Aug 17, 2010
Can't wait for the result! What is the paper stating though? We all want to know if P=NP or not!
sender
not rated yet Aug 17, 2010
it would seem to be easiest objectified as a parallelogram in P=NP where P greater than 0 or (1)NP
xponen
not rated yet Aug 17, 2010
If P=NP, then, given time; our brain can solve all the problem in the universe... no need for alien to come and give inspiration to save us (from our problem).

I think it is more plausible that P (is)!=NP, and our brain is just copying solution from the universe/its-environment... hence, our brain won't be original, the solution is a copy, but yet; the brain did solve some problem, minor one.

-For example; If I play a chess game and I'm good at it, then it is most probably that it is because I practice and I play by example (over my entire lifetime), rather than figuring out all the winning move all by myself, in my mind. I don't think even the most powerful computing substrate (like the brain) can ever figure out EVERYTHING by itself.
gwrede
1 / 5 (1) Aug 17, 2010
Skimmed through the paper. I was expecting reams after reams of intractable formulas full of alien glyphs, but there is almost no math at all!

It is an interesting and entertaining read, even when one can't claim an adequate understanding of the text.

Personally, I'd be more at ease if P=NP is proved wrong than the opposite. I hope the paper is right.
Doug_Huffman
1 / 5 (1) Aug 17, 2010
I only just downloaded the paper, to note the title that seems to suggest the author's position
P≠NP
El_Nose
5 / 5 (2) Aug 17, 2010
just to end the confusion the author of the paper is attempting to prove P != NP
gunslingor1
not rated yet Aug 17, 2010
this doesn't sound right to me:
"The Clay Mathematical Institute offers the following problem to illustrate NP: you have a list of 400 university students to be accommodated but there is only room in the dormitory for 100 students. The Dean has provided a list of pairs of incompatible students who cannot be on the final list. This is an NP-problem because it is extremely difficult to go through all possible combinations to come up with a list, but very easy to verify once a list is obtained. According to CMI the number of possible combinations is greater than the number of atoms in the universe."

sounds like a mistatement of the problem. I don't think the final list would be infinite, how could it be, you only have room for 100 students?

Valentiinro
1 / 5 (1) Aug 17, 2010
Its the combination of students that's the issue. 400 factorial or something? Furthermore the number of atoms in the universe is not supposed to be infinite.
gunslingor1
not rated yet Aug 17, 2010
Valentiinro,

Yeah, I realized that after posting. Problem is that I still think the example is unrepresentative of the problem. How many pairs could there really be that cannot be together? if it's anywhere close to 400!, then the list couldn't even have been generated.

Interesting though. This is my first exposer to this problem, though it does sound familiar.

I'm gonna study up before I look further like a moron.
stealthc
not rated yet Aug 17, 2010
200 to the power of 2 combinations in the list.

That number could so be generated. At least a heck of alot easier than the recent refinement to pi that was calculated.
xponen
not rated yet Aug 17, 2010
As an example; a tic-tac-toe game has a 3x3 space, but it has 26,830 way to play the game!. An AI did not "think" (when it try to find solution), instead, it "search" all this possible combination to get the simple winning condition of 3-in-a-row. -As a human, we do not see such complexity, we see tic-tac-toe as a very tiny tiny game with a "few bytes of memory space... and is a "duh..." game", like that.
neoabraxas
not rated yet Aug 17, 2010
the link to the actual paper is not working
gunslingor1
not rated yet Aug 17, 2010
As an example; a tic-tac-toe game has a 3x3 space, but it has 26,830 way to play the game!. An AI did not "think" (when it try to find solution), instead, it "search" all this possible combination to get the simple winning condition of 3-in-a-row. -As a human, we do not see such complexity, we see tic-tac-toe as a very tiny tiny game with a "few bytes of memory space... and is a "duh..." game", like that.


there is a very simple algorithum I figured out (others probably figured this out as well) that will guarantee you never lose.
Jovovic
5 / 5 (1) Aug 17, 2010
Been there! - a statistical way showing how, where, and why we end up with uncertainties:

http://blog.resea...mplexity
dsa
not rated yet Aug 17, 2010
P is not equal to NP

That is what the guy is proving:
http://www.hpl.hp...lalikar/
http://www.hpl.hp...lalikar/Papers/pnp_synopsis.pdf
abhishekbt
5 / 5 (1) Aug 18, 2010
To add-on, the no of solutions to the problem is given by nPr where n is the total group, P is formula for permutation and r is the no. of subgroups.

So, the solution will be something like 400! / 2! which comes out to be on the order of 3.2 x 10^868.

A quick Wikipedia check tell me that the estimated no. of atoms in the universe is in the order of 10^80.

Hope this helps realise the 'gravity' of the situation!
Jarek
5 / 5 (1) Aug 18, 2010
Such proof would have to cover all classes of approaches … like continuous global optimization.
For example in 3SAT problem we have to valuate variables to fulfill all alternatives of triples of these variables or their negations – look that
(x OR y) can be changed into optimizing

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

and analogously seven terms for alternative of three variables. Finding global minimum of sum of such polynomials for all terms, would solve our problem. ( www.scienceforums...mputers/ )

It’s going out of standard combinatorial techniques to continuous world using gradient methods, local minims removing methods, evolutionary algorithms … it’s completely different realm: numerical analysis.
Such proof could work on concrete valuations, but here we work between them.
Does/can it cover also continuous approaches?
ElasfarSovereign
not rated yet Aug 29, 2010
Apparently his calculations were incorrect. If you click on one of the blogs of another scientist mentioned in this story, it will tell you the guy was wrong. So we still have to wonder is P=NP or not. Dammit!
ElasfarSovereign
not rated yet Aug 29, 2010
This is the scientific follow up to the story if you're interested.
MIT's technology review.
ElasfarSovereign
not rated yet Aug 29, 2010
In my marriage, P DEFINITELY did NOT equal NP!
Jarek
not rated yet Aug 29, 2010
ElasfarSovereign, look one post up - if you can just optimize degree 14 (can get down to 8) real nonnegative polynomial in polynomial time of variables (gradient methods?), you get million bucks ...
... and it looks new - there was needed huge amount of constrains earlier ... http://groups.goo...8?hl=en#
gwrede
1 / 5 (1) Sep 08, 2010
@Jarek: standing in an empty lab, one can easily conceive of your solution to ElasfarSovereign's problem.

Try doing it standing in your hallway, with wife yelling, kids yelling, landlord sent thugs in your face, and a 2-week notice from the office.

So, do us a favor: solve the thing, get rich -- and as a side effect, help us out!

I'd call that "a favor to mankind, way surpassing those for which you get a Nobel Prize"!
Jarek
not rated yet Sep 09, 2010
Even if it's possible(???), would such proof change practically more than destroying huge systematics? As I know, AKS still isn't used ...
More 'helpful' (and creating chaos...) would be a practical way to solve such problems - this numerical analysis translation could be a good start ... it has landed on my huge pile of problems I'm going to look closer sometime ...
But generally, there is also another way - just try to use physics, which have huge unexplored computability capability ... and it could give more options than quantum calculations, like for example:
http://www.electr...ter.html

More news stories

Newlyweds, be careful what you wish for

A statistical analysis of the gift "fulfillments" at several hundred online wedding gift registries suggests that wedding guests are caught between a rock and a hard place when it comes to buying an appropriate gift for the ...

Can new understanding avert tragedy?

As a boy growing up in Syracuse, NY, Sol Hsiang ran an experiment for a school project testing whether plants grow better sprinkled with water vs orange juice. Today, 20 years later, he applies complex statistical ...

Roman dig 'transforms understanding' of ancient port

(Phys.org) —Researchers from the universities of Cambridge and Southampton have discovered a new section of the boundary wall of the ancient Roman port of Ostia, proving the city was much larger than previously ...

Crowd-sourcing Britain's Bronze Age

A new joint project by the British Museum and the UCL Institute of Archaeology is seeking online contributions from members of the public to enhance a major British Bronze Age archive and artefact collection.

Better thermal-imaging lens from waste sulfur

Sulfur left over from refining fossil fuels can be transformed into cheap, lightweight, plastic lenses for infrared devices, including night-vision goggles, a University of Arizona-led international team ...

Hackathon team's GoogolPlex gives Siri extra powers

(Phys.org) —Four freshmen at the University of Pennsylvania have taken Apple's personal assistant Siri to behave as a graduate-level executive assistant which, when asked, is capable of adjusting the temperature ...