Technology Review
A proposed "proof" is probably a bust--but even failed attempts can advance computer science.
Programmers and computer scientists have been buzzing for the past week about the latest attempt to solve one of the most vexing questions in computer science: the so-called "P versus NP problem."
Vinay Deolalikar, a research scientist at HP Labs in Palo Alto, CA, posted his "proof" online and sent it to several experts in the field on August 6. Colleagues immediately began dissecting the proof on academic blogs and wikis. Early reactions were respectful but skeptical, and the current consensus is that Deolalikar's approach is fundamentally flawed.
A solid proof would earn Deolalikar fame and fortune. The Clay Mathematics Institute in Cambridge, MA, has named "P versus NP" as one of its "Millennium" problems, and offers $1 million to anyone who provides a verified proof.
But "P versus NP" is more than just an abstract mathematical puzzle. It seeks to determine--once and for all--which kinds of problems can be solved by computers, and which kinds cannot. "P"-class problems are "easy" for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for "NP" problems, a solution might be very hard to find--perhaps requiring billions of years' worth of computation--but once found, it is easily checked. (Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it.)
NP-class problems include many pattern-matching and optimization problems that are of great practical interest, such as determining the optimal arrangement of transistors on a silicon chip, developing accurate financial-forecasting models, or analyzing protein-folding behavior in a cell.
The "P versus NP problem" asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem. If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers' problem-solving powers will remain fundamentally and permanently limited. Practical experience overwhelmingly suggests that P does not equal NP. But until someone provides a sound mathematical proof, the validity of the assumption remains open to question.
Even if Deolalikar's proof were found to be sound, then the question remains--what impact would such a proof have on relevant areas of computing?
Superficially, one might think the answer is "not much." "Proving that P does not equal NP would just confirm what almost everyone already assumes to be true for practical purposes," explains Scott Aaronson, a complexity researcher at MIT's Computer Science and Artificial Intelligence Laboratory.
Did D-Wave really demonstrate "the world's first commercial quantum computer"?
Our entire information society rests on a fragile foundation that mathematicians are racing to dismantle.
Mathematical definition of P & NP
What's the mathematical definition of P & NP?
The article was very qualitative about the definition.
Re: Mathematical definition of P & NP
Roughly speaking...
A problem is in P if there is a normal program that solves it in polynomial time, that is in time given by a fixed polynomial in the size of the input.
A problem is in NP if there is a program that is allowed to continually guess as it computes a result, and some sequence of guesses will produce (and verify) the correct result in polynomial time. Since it is trivial to guess results, all that is necessary is that there is a normal program that can verify a result in polynomial time (with the polynomial based on the size of the input, not the result).
Most current public key cryptography is based on the difficulty of factoring integers. It is well known that integer factoring is in NP, because verifying a factorization merely requires multiplication, and even the schoolboy multiplication algorithm is in P. But it is not known if factoring is NP-complete, so proving P is not equal to NP won't necessarily prove that factoring isn't in P, and conversely, finding a P time algorithm for factoring won't prove P=NP.
NOTE: A problem is NP-complete if an instance of any NP problem can be converted to an instance of the NP-complete problem in polynomial time. Many NP-complete problems are known.
They should just give the million dollar prize to the guy who develops a quantum computer that can break public key encryption. From what I've read many "NP" problems for classical computers would be trivial for quantum computers. I say they should just build one already and see if quantum computers are what they claim them to be and how many NP problems quantum computers can solve in P time.
The current P-vs-NP debate,
Has P being used to equate,
The problems involved,
With NP being resolved,
To finding a solution or suffering its fate.
'''"P"-class problems are "easy" for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for "NP" problems, a solution might be very hard to find--perhaps requiring billions of years' worth of computation--but once found, it is easily checked. '''
The use of the words 'for computers' is kinda annoying in the above. If a non-computer can consistently and easily solve a problem, then an algorithm can be constructed for the computer to easily solve the problem.
The gotcha there is that scientists still have a poor understanding of how the brain works fundamentally. Sure, they can produce basic neural networks, but on a fundamental level these are still classical in nature. The brain does not function as a classical computer, and may very well function as a quantum computer. If scientists can replicate how the brain conducts computations, they will be able to achieve NP algorithms in P time.
"The brain does not function as a classical computer, and may very well function as a quantum computer. If scientists can replicate how the brain conducts computations, they will be able to achieve NP algorithms in P time."
If you cannot give us the answer for 1000! (or gazillion! for that matter) instantly, your brain is not a quantum computer.
Haha. If that kind of programming can be done then every single engineer in the world- software and hardware, would be out of a job because this so-called "algorithm" would make these machines engineer everything else...
If you have ever seen how "stupid" automatic place and route programs for ICs work then you'd have a slightly different opinion.
Might we say that Artificial Conscience is a class NP problem ?
This practically does not matter
I still don't see the practical connection. Proving this is a big deal academically but that's about it. If this is proved one way or another, is computing technology going to evolve any faster or slower (or any differently) because of it? I don't think so. If someone thinks otherwise please tell me how.
It's like proving whether there could be FTL space travel or not. So what?
Re: This practically does not matter
P != NP would not have much of an impact on most research, it will simply allow us to fully move our attention away from trying to solve NP hard problems and instead trying to figure out ways to work around it instead.
P = NP on the other hand would have a much larger effect on the scientific community as a whole. For instance, we could invalidate the need for mathematicians, because it would be possible to derive the proof for any mathematical statement instantly. It would also disprove the existenece of one-way functions, which would have an enormous effect on the field of cryptology.
One more comment I'd like to make, the article states implies that our inability to efficiently factor huge composite numbers is because P is probably not equal to NP, however since the factoring problem is not NP-Complete, this is actually not the reason our algorithms are inefficient.
It is theoretically possible to factor in Polynomial time, the only problem is that it requires the use of quantum computing, and nobody has built a quantum computer big enough to factor anything above a few qubits in length.
Worth noting, problems that ARE NP-Complete can't seem to be cracked by quantum computing yet, and it is THOSE problems towards which a proof of P=NP or P!=NP would be applicable
Relativity in Computational complexity
I have solved this question with the help of of relativity in computational complexity and posted the solution on my blog..........Kindly have a look inside
Here is the link: http://solutionpversusnp.blogspot.com/
Manufacturing in the United States is in trouble. That's bad news not just for the country's economy but for the future of innovation.
This document is part of the “How-To Guide for Most Common Measurements” centralized resource portal. This tutorial provides a detailed guide for measurement and device considerations to take temperature measurements using thermocouples. Get an introduction to thermocouples, which are inexpensive sensing devices widely used with PC-based data acquisition systems. Also review some specific thermocouple examples and learn how thermocouples work and ways to integrate them into a data acquisition measurement system.
View full PDF >
Listen to story > 
On Twitter
Become a Fan on Facebook
Subscribe to the Feed
lund1967
8 Comments
Proving a Negative
I don't understand why "proving a negative is just incredibly hard."
To prove N does not equal NP, all you have to do is prove that ONE element of NP is not an element of P.
To prove that N does equal NP, you would have to prove that EVERY element of NP is also an element of P, and that every element of P is an element of NP.
Reply
ms
190 Comments
Re: Proving a Negative
Every element of P is trivially an element of NP. To prove P = NP it would merely suffice to show one NP-complete problem is in P; which would probably mean finding a deterministic polynomial-time algorithm for solving some NP-complete problem (though it might be possible to prove that there is such an algorithm without actually finding it).
Proving P is not equal to NP means showing that no such P algorithm exists.
Reply