Explained: P vs. NP

The most notorious problem in theoretical computer science remains open, but the attempts to solve it have led to profound insights.

Science and technology journalists pride themselves on the ability to explain complicated ideas in accessible ways, but there are some technical principles that we encounter so often in our reporting that paraphrasing them or writing around them begins to feel like missing a big part of the story. So in a new series of articles called "Explained," MIT News Office staff will explain some of the core ideas in the areas they cover, as reference points for future reporting on MIT research.

In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a dark surface etched with green gridlines and strewn with geometric shapes, above which hover strange equations. One of these is the deceptively simple assertion that P = NP.

In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. Roughly speaking, P is a set of relatively easy problems, and NP is a set that includes what seem to be very, very hard problems, so P = NP would imply that the apparently hard problems actually have relatively easy solutions. But the details are more complicated.

Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.

Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: there’s no way around that. But if it simply keeps a record of the largest number it’s seen so far, it has to look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it’s handling — which computer scientists designate N. Of course, most algorithms are more complicated, and thus less efficient, than the one for finding the largest number in a list; but many common algorithms have execution times proportional to N2, or N times the logarithm of N, or the like.

A mathematical expression that involves N’s and N2s and N’s raised to other powers is called a polynomial, and that’s what the “P” in “P = NP” stands for. P is the set of problems whose solution times are proportional to polynomials involving N's.

Obviously, an algorithm whose execution time is proportional to N3 is slower than one whose execution time is proportional to N. But such differences dwindle to insignificance compared to another distinction, between polynomial expressions — where N is the number being raised to a power — and expressions where a number is raised to the Nth power, like, say, 2N.

If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N3 takes almost three hours. But an algorithm whose execution time is proportional to 2N takes 300 quintillion years. And that discrepancy gets much, much worse the larger N grows.

NP (which stands for nondeterministic polynomial time) is the set of problems whose solutions can be verified in polynomial time. But as far as anyone can tell, many of those problems take exponential time to solve. Perhaps the most famous exponential-time problem in NP, for example, is finding prime factors of a large number. Verifying a solution just requires multiplication, but solving the problem seems to require systematically trying out lots of candidates.

So the question “Does P equal NP?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?” Part of the question’s allure is that the vast majority of NP problems whose solutions seem to require exponential time are what’s called NP-complete, meaning that a polynomial-time solution to one can be adapted to solve all the others. And in real life, NP-complete problems are fairly common, especially in large scheduling tasks. The most famous NP-complete problem, for instance, is the so-called traveling-salesman problem: given N cities and the distances between them, can you find a route that hits all of them but is shorter than … whatever limit you choose to set?

Given that P probably doesn’t equal NP, however — that efficient solutions to NP problems will probably never be found — what’s all the fuss about? Michael Sipser, the head of the MIT Department of Mathematics and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group (TOC), says that the P-versus-NP problem is important for deepening our understanding of computational complexity.

“A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says.

Similarly, Sipser says, “the excitement around quantum computation really boiled over when Peter Shor” — another TOC member — “discovered a method for factoring numbers on a quantum computer. Peter's breakthrough inspired an enormous amount of research both in the computer science community and in the physics community.” Indeed, for a while, Shor’s discovery sparked the hope that quantum computers, which exploit the counterintuitive properties of extremely small particles of matter, could solve NP-complete problems in polynomial time. But that now seems unlikely: the factoring problem is actually one of the few hard NP problems that is not known to be NP-complete.

Sipser also says that “the P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful. I think it has helped bridge the mathematics and computer science communities.”

But if, as Sipser says, “complexity adds a new wrinkle on old problems” in mathematics, it’s changed the questions that computer science asks. “When you’re faced with a new computational problem,” Sipser says, “what the theory of NP-completeness offers you is, instead of spending all of your time looking for a fast algorithm, you can spend half your time looking for a fast algorithm and the other half of your time looking for a proof of NP-completeness.”

Sipser points out that some algorithms for NP-complete problems exhibit exponential complexity only in the worst-case scenario and that, in the average case, they can be more efficient than polynomial-time algorithms. But even there, NP-completeness “tells you something very specific,” Sipser says. “It tells you that if you’re going to look for an algorithm that’s going to work in every case and give you the best solution, you’re doomed: don’t even try. That’s useful information.”

N=1

Donuts = MMMMmmm..

That is the only true homer simpson equation.

As time approches infinity P=NP, the problem is really solving a relative problem in a non-relative plain, in this case infinte time.

If Time reaches infinite amounts, it's only logical to assume that every possible option to solving the problem has been exhasted, and eventually a solution, or in some cases the lack there-of would be discovered.

Also given an infinite amount of time and a finite set of options to derive the solution it's only logical to beleive that not only would the solution be discovered, but also the most easiest method at arriving at said solution.... thus P=NP

To be totally honest string theory pretty much makes this NP=P, but I don't think we have enough comment space for that.

P=NP if P = 2*pi radians or 360 degrees and N is an integer value....or, in fact, there is a family of similar solutions if P= k * 2pi where 'k' is any integer value.

Pi = Not Pie

((P=NP)=NP)=P

I have discovered a truly marvelous proof of this, which this comment form is too narrow to contain.

I like turtles.

p=o,and or n=0,and or both = 0.

??????????

It's like when you try to make a chess-playing program. You have to either go with total brute force, trying every possible move for each side all the way to the end before deciding your first move, which takes the life of the Universe or something, or you have to be satisfied with looking ahead n moves only. But the rub is that at the nth move you have to evaluate the board, and if it's not a mate you have to assign a quality score to the position, which is insanely impossible, since for instance a position that has one queen less than another would have to be given a far lower score, yet that move might be a queen sacrifice that wins if only you had gone to the n+1 or n+2 level to check. So chess is easy to compute that somebody won, but impossible to find a way to win in polynomial time. QED, and don't waste your life on silly kid games.

Assume P=NP

Divide both sides by P.

therefore 1=N

Hence P=NP only if N=1

P!=NP for N>1

You can't divide both sides by P without considering that P could equal 0.

Corrected proof:

P = NP

NP - P = 0

P(N - 1) = 0

P = 0, N = 1.

i.e. [If P and N were variables],

P = NP if and only if P = 0 OR N = 1.

Why is such a question posed about form in the first place, I mean like an attempt to encapsulate a class of 'closed form'?

We can dismiss with this petty algebraic mockery assuming P, N, or NP are the variables and their product.

Mathematicians, like the Geologists, have simply monikered their own "K.T. Boundary"; and the mathematicians have called it their P.'=' N.P. boundary for their philosophy. So put away your graphic calculators you are way..way..way, out of your league. Please observe:

Title:

Handbook of theoretical computer science / edited by Jan van Leeuwen.

Publisher:

Amsterdam ; New York : Elsevier ; Cambridge, Mass. : MIT Press, 1990.

ISBN:

0262220407 (MIT Press : set)

0262220385 (MIT Press : v. A)

0262220393 (MIT Press : v. B)

0444880755 (U.S. : set)

0444880712 (U.S. : v. A)

0444880747 (U.S. : v. B)

I noticed in the video lecture of P vs NP by Mr. Sipser that the analogy used was that of finding a needle in a hay stack. And that the way you could find it easily is to simply use a magnet. This analogy has some flaws in that the needle has different properties than the hay does, it's metal. You could burn the hay stack but that requires you to destroy all other possibilities, you lose information. You could use a metal detector but anyone who's ever used one knows that you don't find what you're looking for immediately; this is what probabilities do for you.

P=NP has been solved using Energy Loop Theory formulation... http://www.google.com/search?q...

From a novel theoretical perspective in the book, THE OBELUS SET THEORY OF EQUITY DISTRIBUTION , set concept(s) of the fundamental process of sharing has been used to provide a simple proof for the equality or non-equality between the class of P and NP class. It turns out that P is equal to NP!

I can't believe that the author of this educational post used the symbol "N" in an attempt to clarify P vs. NP. What a hot mess! In P vs. NP, "N" stands for "non" as in non-poynomial. To obfuscate this already confusing topic by using N to denote "the number of operations" is more than a little laughable. Especially, when the whole point of this series is "explanation". Are there any editors on the staff? Peer review? A girlfriend or husband or co-worker willing to check for clarity?

the traveling salesman is not n!but

the sum of (n-i) from i=0 to n-1

proof of goldbach

take an nxn tableas n goes to infinity.

p(n) is the nth prime. process al p(n),n=> 2.process p(k)+p(n) in column

k-1 starting in row p(k)+p(2).example:

column1 Column k-1

p(2)+p(2)

p(2)+p(3)

.

. p(k)+p(2)

. p(k)+P(3)

.

.

P(2)+p(n) .

p(k)+p(n)

etc.for an inite number of rows an columns. For goldbach to be false there

would have to be at least one empty even row. this procedure makes an empty

even row impossible. therefore all even numbers=>6 are accounted for. then just add 2+2=4

proof of goldbach

a nXn table as n goes to infinity

indentation correction

p(k)+p(n) ,n=>2 is processed in column k-1 starting in row p(k)+p(2) example

column 1...... column k-1

p(2)+p(2)

p(2)+p(3)

.

........... p(k)+p(2)

........... p(k)+p(2)

.

P(2)+p(n)

............. p(k)+p(n)

.

.

etC. for an infinite number of rows and an infinite number of columns. For Goldbach to be false there would have to be at least one empty even row. This

procedure makes an empty even row impossible. Therefore all even numbers

=> 6 are accounted for. Then just add

2+2=4

If you Google... P = NP Math Question you'll find its worth a million if solved.

With the help of my son theryn.... I think we solved it.

N = 0

P = P

P = 0P

0 = infi

Hence P = NP if NP = infi 0

P=NP is nothing or space.

Space = Time

Time = Light

Light = Time Space

P = Light NP = Time Space

Solution is

Light >Time Space or P= Measured Time Space

We immediately see:

One algorithm to deliver a general NP problem/question and one algorithm to provide a general solution. versus... One algorithm to deliver a particular example and one algorithm to verify that particular example.

Therefore we have an analysis required for four algorithms of which only three can necessarily be considered verifiably P and already fully grounded on a particular axiomatic foundation. There is still one open algorithm to fully establish and fully account for, i.e., the general proof.

So, P = NP requires circle-squaring for now, therefore P not= NP until a general polynomial time NP proof is found, if that can be done. Finally, since this analysis itself requires an algorithm, we may be dealing with quintic impossibility here.

Seems to me mathematics is a field limited to imagination.

P = n p

Water= 5 H20 thinking of it in this nature you may make different connections as to possible solution sets to this problem. The only relationships or values these variables have are the ones we give them.

So in this instance I have used the common term for water and the Chemical make up and n would be the quantity. Regardless of how much water you have it is still water.

The first choise

A man (Bob) is a Turing machine and a women (Any) is input data. Then transition function is "what he tells them AFTER START" to acceptance state.

For a deterministic Turing machine the inputa data is Any.

For a nodeterministic Turing machine Bob has before START two women: Any and Ana and he must chosse befor START one of them.

If he choose Any is ok, but if he chooses ANA?,

Can we compare the complexity of two problems?

That means Nondeterministic Turing machine input change prior to START?

Smiling man. It's just an anecdote

I believe that P=NP; I am 12 years old but I still have a view. NP is non deterministic but that is because we cannot work it out. Our computers cannot solve it. we cannot solve them quickly... supposedly; what if there is a solution to these which do not make us go through every possibility. Take the millennium problem for instance: (I may not be correct but bare with me) It seems so hard because we have 400 students to sort. But what if we have a method: What I have done is:

1. Put the two sections/amounts that you have to split ,which is students in this case, into ratio: 300:100 which is 3:1

2. Put this into fraction: 3/1 which is 3

3. Put 3 to the power of the normal amount which is 3^400

This could potentially be the answer but I am not guaranteeing anything.

3. Then do

Its unlikely that P=NP with classical computation, but I think we might find an algorithm to do it with quantum computers. Somehow N qubits can do 2^N (or more) operations simultaneously, and physicists still have no clear answer as to what is doing that work. Some will straight up tell you, like David Deutsch, that the ops are running in parallel universes, other evidence points to quantum systems being influenced by future events.

The assumption going into P=NP is that future computations cannot influence current ones. If Quantum Physics shows that that's EXACTLY how nature does things, you can have P=NP: the eventual solution could be used to generate itself!.

The answer is simple. -pi alpha

I wish to announce the genuine solution to the P vs NP Problem (that is P does not equal NP). The solution by solid proof is included, among other solutions, in my
published number theory, free-accessed at:

www.saitabooks.eu/2015/01/eboo...

Having proven what a (pure) number is, the essential criterion has come to surface; the true numeric function of addition/subtraction, and the fact that the
multiplication/division has to absolutely be interpreted as addition/subtraction (unit-by-unit elementary function) so that there actually exists a function of multiplication or division. Simple: the computer counts 1 2 3 4 5, but it doesn't count 12.345, which constitutes a division, thus a factorial deed. The numeric nature is this of addition, not multiplication. Multiplication is the basis for any factorial counting. Yet, e.g. 2x3=6 cannot be considered as existent unless there exists the statement 2+2+2=6. The latter holds all the essence of 6. The former bears no meaning at all when it is about pure numbers.

Responsible critique is always welcome!

If I have understood the idea it is not a problem of computation so much as expertise. A chef knowing what ingredient is missing or a perfumer knowing what ingredients are included?

Does it not depend on the starting point ?because when we check the solution we have already assume or built the algorithm. so it doesnot start at the same level of computation than solving the problem.To check the problem doesnot start at the same level of computation. So it sometime is not even the same problem. So n and np can be either way. Meaning any step could include more or less steps or even same number of step depending on where we start the problem from.

Back to the top