18

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?

Improve this question
1
  • 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, 2012 at 1:25

5 Answers 5

Reset to default
23

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!

Improve this answer
17
  • 4
    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.
    – user28988
    May 16, 2012 at 13:52
  • 7
    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, 2012 at 14:09
  • 7
    Of course the constant factors might be so large to make this just a theoretical problem... for some time.
    – quant_dev
    May 16, 2012 at 14:10
  • 18
    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, 2012 at 14:12
  • 5
    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, 2012 at 15:25
18

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).
Improve this answer
6
  • 3
    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, 2012 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, 2012 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, 2012 at 20:30
  • first time I heard about the principle of Occam's razor. Interesting stuff...
    – UmNyobe
    May 16, 2012 at 22:17
  • 1
    @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, 2012 at 0:44
7

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.

Improve this answer
2
  • 3
    Whilst integer factorization is a difficult problem, it is worth noting that it isn't known to be NP-complete.
    – dan_waterworth
    May 16, 2012 at 14:45
  • 4
    @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, 2012 at 15:24
6

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.

Improve this answer
0

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).

Improve this answer
6
  • 1
    Actually, there exists an explicit reduction algorithm that is in P if and only if P=NP. It consists in iterating over all possible programs and running them in parallel until one finds the solution.
    – Arthur B
    Jun 16, 2014 at 20:07
  • @ArthurB fascinating. Assuming that P=NP, what is the order of the algorithm?
    – emory
    Jun 16, 2014 at 21:14
  • It is unknown, but it is the optimal order. scholarpedia.org/article/Universal_search
    – Arthur B
    Jun 17, 2014 at 0:49
  • 2
    @ArthurB so if P=NP and the reduction algorithm is O(n^99999999) is P=NP still such a big deal?
    – emory
    Jun 19, 2014 at 3:05
  • 1
    It's unfortunate that this was downvoted, when it is correct and the other answers are wrong and silly. Showing that P=NP would only show that fast algorithms must exist; it doesn't change the fact that we haven't found them and have no idea how to.
    – Jim Balter
    Mar 21, 2022 at 20:55

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