The P Versus NP Problem

2009-08-29

in Geek stuff, Science

There are some sorts of problems where it is relatively easy to check that a solution is correct, but hard to find that solution to begin with. For example, it is easy to check whether a large number is the product of two primes (429,496,729 = 19 X 22,605,091), but it is hard to find the factors of a large number. These problems are called ‘NP problems’ in mathematics, because they cannot be solved in polynomial time.

By a quirk of mathematics, if anyone ever comes up with an efficient way to solve one of these NP problems, the technique will be applicable to all such problems. That said, it may be the case that there is no efficient way to solve any of these problems. As such, whether all or none of them are efficiently soluble is an important question in mathematics.

The importance of the problem extends beyond the theoretical realm. For instance, the ‘traveling salesman’ problem is NP. There is a salesman who wants to visit X cities, with as little travel as possible. Finding the quickest route becomes dramatically more difficult as the number of cities increases. If someone could solve the P versus NP problem they could either help Fedex and UPS a lot (if an efficient solution to NP problems is found) or prove that their work will always be challenging (if it is proven that there are none).

This article provides more information on the P versus NP problem.

Report a typo or inaccuracy

{ 14 comments… read them below or add one }

Milan August 29, 2009 at 8:14 pm

Incidentally, if you can either prove that P = NP or that P ≠ NP. the Clay Math Institute will give you $1 million.

Tristan August 30, 2009 at 2:39 am

Are you sure the travelling sales problem has any importance to mail delivery services? Can you explain how it would help them?

. August 30, 2009 at 10:51 am

Travelling salesman problem
From Wikipedia, the free encyclopedia

The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as genome sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.

. August 30, 2009 at 10:54 am

VRP is an operational decision support tool for geographically distributed businesses, such as the delivery of goods from a depot (or multiple depots) to customers by a fleet of trucks. We can use VRP to find the optimal routes for delivery trucks on the road network that minimize the number of trucks required, under constraints on capacity, time, and customer demand. VRP was developed on the basis of heuristics for the traveling salesman problem (TSP), which were developed mainly for solving problems in manufacturing, such as the printed-circuit-board-drilling problem. We succeeded in transforming the vehicle routing problem into the TSP, and applied our expertise in the TSP to vehicle routing. We are now developing prototype solutions for several customers.

. August 30, 2009 at 10:55 am

A multi-depot travelling salesman problem and its iterative and integrated approaches

This paper formulates a logistics distribution problem as the multi-depot travelling salesman problem (MDTSP). The decision makers not only have to determine the travelling sequence of the salesman for delivering finished products from a warehouse or depot to a customer, but also need to determine which depot stores which type of products so that the total travelling distance is minimised. The MDTSP is similar to the combination of the travelling salesman and quadratic assignment problems. In this paper, the two individual hard problems or models are formulated first. Then, the problems are integrated together, that is, the MDTSP. The MDTSP is constructed as both integer nonlinear and linear programming models. After formulating the models, we verify the integrated models using commercial packages, and most importantly, investigate whether an iterative approach, that is, solving the individual models repeatedly, can generate an optimal solution to the MDTSP.

. August 30, 2009 at 10:57 am

What If P = NP?

To understand the importance of the P versus NP problem let us imagine a world where P = NP. Technically we could have P = NP, but not have practical algorithms for most NP-complete problems. But suppose in fact we do have very quick algorithms for all these problems.

Many focus on the negative, that if P = NP then public-key cryptography becomes impossible. True, but what we will gain from P = NP will make the whole Internet look like a footnote in history.

Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I’m just scratching the surface.

Learning becomes easy by using the principle of Occam’s razor—we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.

P = NP would also have big implications in mathematics. One could find short, fully logical proofs for theorems but these proofs are usually extremely long. But we can use the Occam razor principle to recognize and verify mathematical proofs as typically written in journals. We can then find proofs of theorems that have reasonable length proofs say in under 100 pages. A person who proves P = NP would walk home from the Clay Institute not with $1 million check but with seven (actually six since the Poincaré Conjecture appears solved).

Don’t get your hopes up. Complexity theorists generally believe P ≠ NP and such a beautiful world cannot exist.

R.K. September 1, 2009 at 11:15 am

Proving that P = NP would have some dramatic consequences, especially in mathematics. Apparently, it would allow you to automatically generate proofs for any problem where the proof is of a reasonable length. It’s hard to guess what consequences that would have, both in terms of pure theory and applications.

Decent speech recognition for computers would be a nice start, though.

R.K. September 2, 2009 at 8:42 pm
Mark September 5, 2009 at 9:48 am

Incidentally, factoring is not an NP-complete problem (or at least strongly suspected not to be so). A fast solution to factoring would have no bearing on Travelling Salesman. Shor’s algorithm, for example, solves the factoring problem in polynomial time (provided you have a quantum computer). Quantum computes aren’t known to provide a similar magic bullet for most NP-complete problems.

It raises the question – if factoring isn’t the hardest problem around, why don’t we base encryption schemes on problems known to be harder? As far as I know there is no existing encryption scheme that would only be breakable in polynomial time if P == NP. I believe it’s still an open question. Even if we did have one, it may not be much use because NP is a statement about worst-case complexity, not average case complexity. So an NP encryption scheme might yield messages that were trivial to decrypt most of the time, provided there was at least one possible message that took exponential time to decrypt. Truly secure encryption requires something even harder than an NP-hard problem!

Milan September 5, 2009 at 10:15 am

There are always one-time-pads, though they are not a convenient solution, especially for applications like e-commerce.

. September 22, 2009 at 5:01 pm

Quantum Computer Factors the Number 15

By Bruce Schneier

Shor’s algorithm was first demonstrated in a computing system based on nuclear magnetic resonance — manipulating molecules in a solution with strong magnetic fields. It was later demonstrated with quantum optical methods but with the use of bulk components like mirrors and beam splitters that take up an unwieldy area of several square meters.

Last year, the Bristol researchers showed they could miniaturize this optical setup, building a quantum photonic circuit on a silicon chip mere millimeters square. They replaced mirrors and beam splitters with waveguides that weave their way around the chip and interact to split, reflect, and transmit light through the circuit. They then injected photons into the waveguides to act as their qubits.

Now they’ve put their circuit to work: Using four photons that pass through a sequence of quantum logic gates, the optical circuit helped find the prime factors of the number 15. While the researchers showed that it was possible to solve for the factors, the chip itself didn’t just spit out 5 and 3. Instead, it came up with an answer to the “order-finding routine,” the “computationally hard” part of Shor’s algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time, according to Jeremy O’Brien, a professor of physics and electrical engineering at the University of Bristol. The researchers then finished the computation using an ordinary computer to finally come up with the correct factors.

. September 28, 2009 at 10:19 am

A “Photon Machine Gun” For Quantum Computers

An anonymous reader writes “Generating entangled photons in a reliable way is impossible right now, stalling the development of the optical quantum computers that would use entangled photons as quantum bits (qubits). Because entangled photons can only be produced at random — which takes time — the most powerful optical quantum computing device use only 6 qubits. UK and Israeli quantum physicists have designed a blueprint for a ‘quantum machine gun’ that fires out barrages of entangled photons on demand. They think within a few years this device will be built, and could lead to quantum computing using 20 to 30 qubits. Every additional qubit doubles the computing power, so these quantum computers could outperform any existing classical computer, the researchers say. The quantum machine gun is described as ‘one of the most exciting theoretical proposals I’ve read in five years’ by a leading quantum physicist.” The research was published in Physical Review Letters earlier this month.

Dominick Parrish May 31, 2013 at 1:03 pm

If you take 400 names assign each one an I.Q. and an amount of athletic abilities you could easily provide the 100 students that the dean would pick because it would of course be the top 100 overall in skills then once you receive the list of the 50 incompatible pairs you could put them in list form and move the first half of the list down 1 space and leave the second half alone thus you would have the pairs for the dorms.

anon May 31, 2013 at 5:40 pm

weird spam…

Leave a Comment

You can use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Previous post:

Next post: