P=np

I’ve heard about P=NP in various places, and I’m curious about exactly what this concept is. I’ve also heard about “polynomial time”. What is that?

See here:

NP-Problem

P Versus NP Problem

The link posted is rather technical, so here’s a very, very abbreviated version (see the links that Desmostylus posted for more information).

We’re referring to algorithms here, generally programs that can be executed on a standard computer.

“Time” refers to how long it takes to find the answer, as a function of the size of the input. Time is roughly equivalent to “number of steps” in the program, although I’m skipping some important details. There are a lot of different time classes, a few of which, in increasing complexity are:

Constant Time - the size of the input doesn’t matter: for example, “What is the first element of an (input) list?” – you don’t need to look at the whole list to find out, so it doesn’t matter how long it is.

Polynomial Time - the number of steps required can be calculated as a polynomial in the size of the input (n): A * n + B * n^2 + C * n^3 … note that “n” (the input size) never appears as an exponent. A large number of algorithms execute in polynomial time: for example “What is the middle element of an (input) list?” – you need to see the whole list in order to know how many elements are in it, but then it’s just a single step to find the middle element. Similarly, “What is the sum of elements of a list?”

Exponential Time - the number of steps can is an exponential function of the input size A * x^n. “Print out all the combinations of the members of a list”, for example.

To answer the first part of your question, let’s consider a classic problem: the travelling salesman problem. The input here consists of a list of cities and distances between them, the problem is to determine the shortest route that passes through all of them. Currently, the best algorithm known is (roughly) to try all combinations of the paths, add them up, and take the shortest one. This would take exponential time.

However, imagine we had a “magical” algorithm that, while “visiting” each city, could somehow try all the paths from that city AT THE SAME TIME. (Alternatively, you have an “oracle” that “knows” the right path at each step). Given such an algorithm, you could solve the problem in polynomial time. This hypothetical computer that can execute an infinite number of paths in a single step is called a “nondeterministic machine.” A problem that can be solved by a non-deterministic algorithm in polynomial time is said to be solvable in “nondeterministic polynomial time”, or NP - time problems. Problems that can be solved by an “ordinary” computer (i.e. one we can actually build) in polynomial time are said to be P - time problems.

Note that I’ve slightly changed the focus from the time it takes to solve a problem to the problem itself. A fundamental question in computer science is: is there a way to solve NP problems in polynomial time on a standard computer? That is: is the set of problems that a standard computer can solve in polynomial time equal the set of problems our hypothetical “nondeterministic” computer can solve in polynomial time?

Succinctly, is the set P equal to the set NP, or is it a (strict) subset? The current thinking is, I believe, that P is NOT equal to NP. This matches our intuition that giving a computer additional “powers” should increase it’s computing function. But the problem is the classic case of having to prove a negative: Can you show that there is NO polynomial time algorithm which will solve the hardest NP problems? It’s stymied computer scientists for decades.

One last tidbit here for completeness: The “hardest” set of NP problems are called “NP-complete”, and it’s provable that you can convert any NP-complete problem into any other in polynomial time. Therefore, since “polynomial + polynomial = polynomial”, if you can find that ANY NP-complete (not just NP) problem is also in P, you’ve found that they all are.

P=np

Problem? no problem!

Or, a problem is no problem to have. It’s Zen.

PS-- My own personal koan-- “Zen isn’t Bullshit, but it seems precisely like it.”