Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am preparing for a test and I can't find a clear answer on the question: What would be the impact of proving that PTIME=NPTIME. I checked wikipedia and it just mentioned that it would have "profound impact on maths,AI,algorithms.." etc.

Anyone can give me an answer?

share|improve this question
This in no way has anything to do with software development. I closed for now but asked the mods at Math.StackExchange if they would like me to migrate this for you. –  maple_shaft May 17 '12 at 1:25
add comment

closed as off topic by TMN, maple_shaft May 17 '12 at 1:24

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

5 Answers

up vote 16 down vote accepted

First thing that comes to mind is that the security of public-key cryptography currently depends on being unable to brute-force math problems that are in the NP difficulty class. If P = NP, everything that depends on PKC (including HTTPS, which means the entire modern, worldwide ecommerce infrastructure) would have to be reworked!

share|improve this answer
It would ensure that there are algorithms that run in polynomial time. It would then only be a countdown to finding those algorithms and then kaboom so to speak. –  World Engineer May 16 '12 at 13:52
A proof would involve finding a polynomial time algorithm for an NP-complete problem. And when you find one polynomial algorithm, you can use it to solve all other NP-complete problems by reducing the problems to a common form. This means that a proof for P=NP and algorithms that use it will appear at the same time. –  Oleksi May 16 '12 at 14:09
Of course the constant factors might be so large to make this just a theoretical problem... for some time. –  quant_dev May 16 '12 at 14:10
When we find such an algorithm it might still have a horribly high constant factor or be of a tremendous degree (n^10000 is polynomial, but for many practical purposes it is much worse than a small exponential complexity). Of course it would be a warning sign for everybody to move away from the old methods, like we moved away from DES before it was proven to be solvable, but world economy wouldn't immediately collapse. Just think of money itself: everyone ultimately knows that it doesn't actually work unless you believe in it, but global trade still kind of works fine. –  Kilian Foth May 16 '12 at 14:12
We would probably resort to using one-time pads. Amazon could mail you a 1-Gig thumbdrive that would work with its site and hold you over for the rest of your life. –  Macneil May 16 '12 at 15:25
show 12 more comments

This is covered in The Status of the P Versus NP Problem. Definitely worth a read.

A few salient points from the article (quoted from the What If P = NP? section):

  • Public-key cryptography becomes impossible.
  • 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.
  • 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).
share|improve this answer
I fail to see how P=NP implies public key cryptography is impossible. It suggests (but does not imply) that current implementations are not as hard to break as we previously thought. But as others have pointed out, if the relevant constants in an optimal time reduction algorithm are extremely large, then P=NP would not have any impact on public key cryptography. –  emory May 16 '12 at 19:10
+1 for the third bullet point - everyone knows that P=NP would affect crypto, but for some reason you rarely hear about how it would affect literally every other computing discipline on the planet. –  BlueRaja - Danny Pflughoeft May 16 '12 at 20:10
@emory: I won't pretend to be an expert, but my understanding is that if such an algorithm was found, even with a fairly high constant, we would have to totally rethink our approach. Also, who's to say once an algorithm is found, we can't find another one with a smaller constant? One algorithm would unlock all other NP-complete problems too. So the immediate effect may not be large, but a lot of thought would be have to put into changing all existing systems. –  vinaykola May 16 '12 at 20:30
first time I heard about the principle of Occam's razor. Interesting stuff... –  UmNyobe May 16 '12 at 22:17
@vinaykola proving P=NP does not imply finding an algorithm. Of course finding an algorithm would be the most straightforward (but not the only) way to prove P=NP and then if the constants were reasonable, we could get into the issues you raised. –  emory May 17 '12 at 0:44
add comment

Most NP complete problems have "interesting" real life applications. P=NP will have lot of consequences :

  • It will be possible to solve exactly optimization problems which are currently approximated. This is the case of the Travelling Salesman Problem and Job Scheduling Problem
  • It breaks some security measures which are based on the fact that required computational time is enormous. For instance lots of encryption schemes and algorithms in cryptography are based on number factorization, the best known algorithm having exponential complexity. These algorithms will becomes useless if a polynomial algorithm is found.

The bottom line is on the nature of the problems known to be NP-complete. These are not just problems created by few scientists in a remote location to entertain each other. They can be expressed in business terms. In fact, some job interviewers like to conceal NP-complete problems in their questions in order to test candidates.

share|improve this answer
Whilst integer factorization is a difficult problem, it is worth noting that it isn't known to be NP-complete. –  dan_waterworth May 16 '12 at 14:45
@dan_waterworth: It isn't known if integer factorization is NP-hard, but it is known that it is in NP. [Often it seems people say "NP-complete" when they mean "in NP" or "NP-hard". In a way, it would be like someone saying "less than or equal to" in a situation where "less than" would be more precise.] –  Macneil May 16 '12 at 15:24
add comment

These possibilities are covered in Impagliazzo's Five Worlds.

Here's some takeaway points:

  • Artificial Intelligence would be able to make a giant leap. For example, with enough "training data," the shortest-circuits to produce the correct outputs from the inputs would represent the best method of translation. In particular, it would become trivial to have perfect speech recognition and language translation. Taking this idea further, if your training data is Oscar winning movies, it can generate more Oscar winning movies for you.

  • Algorithms as taught in schools would be radically different. Instead of learning so many different algorithmic techniques, courses would focus on reducing problems to verification of correct answers. This would greatly simplify programming.

  • The economy would become vastly more efficient. There would be disruption, including maybe displacing programmers. The practice of programming itself would be more about gathering training data and less about writing code. Google would have the resources to excel in such a world.

  • Because public key cryptography would be "out," Amazon would need to send you a one-time-pad on a thumb drive in order to do secure transactions.

  • Mathematical proofs could be automatically generated and verified.

Overall, it would introduce a technological singularity; the implications of P=NP would be far reaching. Also, Lance Fortnow addresses this point in a separate blog post that you should read.

share|improve this answer
add comment

The impact of proving P=NP would include renewed interest in finding a reduction algorithm. People would also try to find some lower bounds on the constants associated with the reduction algorithm.

Proving P=NP would not be as significant as other answers claim, because it could come in the form of a zero knowledge proof. Knowing P=NP without knowing the reduction algorithm would be little different than the present situation.

Imagine if someone proved that the reduction algorithm existed but is O(sqrt(n)+2^4096).

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.