6 ms·

Watching this process unfold has been extremely entertaining - solely from the perspective of watching how highly scientific / mathematical communities resolve

Watching this process unfold has been extremely entertaining - solely from the perspective of watching how highly scientific / mathematical communities resolve these types of occurrences. There is a LOT of tip-toeing going on, and it seems there is a very established, methodical, and specific process that is followed by those in these communities. You have to wonder if some of these mannerisms could (should?) apply to open source development :) I've attended college, but I'm not a graduate and never really experienced any of the higher-level mathematical courses, so this proof (and discussions thereof) are completely greek to me. But I can certainly tell that based on the discussions and claims the researcher dropped an A-bomb and the math and CS communities are abuzz. For those that are in my situation - is there any layman's summarization that describes what this proof really means to the computer science community? Even the Wikipedia entry has me lost at the second paragraph.

barrkel 16y ago
To an extreme approximation, problems in P are easy and problems in NP are hard. This is important for e.g. cryptography: its security relies on hard problems staying hard. If it were found that P = NP, it would mean that we would have an easy solution to hard problems. On the other hand, if P != NP, then we could rest assured that the hard problems will stay that way.
- carbocation 16y ago
  I think that is a bit too extreme of an approximation. What if someone proved that all NP problems could be solved in n * 1000^1000 time? That is in polynomial time (linear, in fact), but completely intractable. Edit: removed Big O notation, since my point here is actually that the constant might be so large that you'd never get to a point where the limiting case would matter. Sorry to set off a firestorm.
  - barrkel 16y ago
    I actually removed that point from my comment - that problems in P may be intractable, so it may be academic anyhow. But a way of turning NP-complete problems into problems in P (i.e. P = NP) would hopefully mean that intractable NP problems would be tractable P problems, even if only for relatively small values of n.
    - carbocation 16y ago
      Hopefully true, I agree.
  - jules 16y ago
    O(n * c) = O(n), the whole point of the O-notation.
    - carbocation 16y ago
      No. It's only asymptotically equivalent. If the constant is enormous relative to some absolute measure (say, the number of transistors on earth) then O-notation doesn't meaningfully help you.
      - deleted 16y ago
        [deleted]
      - deleted 16y ago
        [deleted]
      - jacobolus 16y ago
        Wrong. O(n * c) = O(n). The definition of O(n) is: f is in O(n) so long as |f(n)| <= M * |n| for some constant M. Likewise, the definition of O(n * c) would be: f is in O(n * c) so long as |f(n)| <= M' * |n * c| for some constant M'. As you can see, any function f which is in O(n * c) is also in O(n), and vice versa. The entire point of complexity classes is to describe asymptotic behavior. If you want to describe something other than asymptotic behavior, find a different tool.
        carbocation 16y ago
        Despite being correct in the narrow sense, you nevertheless end up being wrong in a broader, more useful sense. I do not disagree with the definition. But you shouldn't rigidly focus on the definition without considering the utility of the notation, and the purpose of the discussion. Big O notation describes the asymptotic behavior of a function when the argument N being passed to it approaches infinity. This is why it is also known as asymptotic notation. Now, since this thread is about practical consequence, there is a severe problem with glibly saying that n * 999^999^999^999^999 will ever remotely resemble n from a practical standpoint. You'll never be able to compute f(1), much less a value of n large enough to be limiting. At any rate, it looks like we both agree that O notation doesn't help you here. My fault for bringing it up.
  - jacobolus 16y ago
    > What if someone proved that all NP problems could be solved in O(n) time? You’re quite confused. NP is (at least) a superset of P, and not all problems in P can be solved in linear time (for example, sorting an arbitrarily long list of random numbers). I think you meant something like O(n^(1000^1000))?
    - carbocation 16y ago
      Not confused, though you are correct that we already know that at least some NP cannot be solved in linear time given that NP is a superset of P. I should have phrased things more narrowly. My point is simply to show that even linear-time problems may be computationally intractable.
  - nandemo 16y ago
    You could still have used big O notation: "what if some NP-hard problems could be solved in O(n^(1000^1000))?" That is polynomial time so those problems would be in P, but in practice they would be intractable.
- blantonl 16y ago
  Barrkel: thank you! Edit: so with this in mind, is it safe to say that the NSA's mathematicians are probably the few individuals in the world most interested in this recent development ? Or, are there other types of problems out there that this proof attempts to address? (Commercial etc)
  - philwelch 16y ago
    Cryptography is a perverse example where you want to create very hard problems (if not impossible) for others to solve while having some means of keeping the problem easy for yourself and individuals you trust. If we had some easy way to solve problems in NP though, I bet there would be tons of productive applications. I'll quote a friend of mine: "That would transform life on earth, and multiply our technological development rate by a factor unimaginable. There's no way of even estimating what could happen if that problem were solved, unless the polynomial conversion made the problem impossible. ....It would also solve the protein-folding problem and all of the quantum state problems. Money is nifty; immortality and a possible stardrive don't suck. The NP problem is the current barrier to human science. 'There's no way to simulate that' is a constant refrain around here." An interesting way of looking at it is that a valid proof that P != NP would be a kick in humanity's balls comparable to Gödel's incompleteness theorem.
    - eru 16y ago
      Only that most people already expect P != NP. But as you say, P = NP would really make things too easy.
  - andreyf 16y ago
    Commercial etc Well, if the opposite had been proven, P = NP, there would be titanic commercial opportunities, but it seems to be the opposite (as most people suspected).
  - hc 16y ago
    no, a proof that P!=NP would most likely have no immediate consequences for engineering ("practical") applications to anyone, the people most interested in resolution of P vs NP are complexity theorists and other theoretical computer scientists
- deleted 16y ago
  [deleted]
- _delirium 16y ago
  Is there actually much cryptography based on NP-hard problems? Neither integer factorization nor elliptic curves are known to be NP-hard, for example. The first part of your statement is still true (if P=NP, then RSA would be breakable in polynomial time), but I don't think the second part is (proving P!=NP doesn't prove that integer factorization is outside P).
  - eru 16y ago
    Cryptography is usually in the intersection between NP and co-NP: NP means a yes-answer is easy to check, co-NP means a no-answer is easy to check. If you are trying to break some encryption you can usually tell quite easily whether you get the right key or not. It would be a major breakthrough (comparable to P=NP) if anyone could show that the intersection of NP and co-NP is equal to NP. Some people tried to make an encryption system out of the knapsack problem (http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack...). It makes a good read about how a promising cryptosystem was broken. Some interesting tid-bit: Even if P != NP, it could still be that most instances of NP-hard problems are easy to solve. (I.e. it's possible that even for NP-hard problems the expected running time is polynomial for all realistic probability distribution of instances. For certain definitions of `realistic'.)
lsb 16y ago
P is the set of all problems that can be verified in time polynomial to the problem space. NP is the set of all problems that can be verified in time polynomial to the problem space with the use of a non-deterministic oracle. Hold that thought. If you have a list of n elements, you can search through the list and check if an element is in that list in n^1 time. If you have a list of n elements, you can check some property on a triplet of numbers in (at worst) n^3 time, looping once for each member of the triplet. I can check that there's a triplet that multiplies to 1337 mod 31337, in a set of n numbers, with three nested loops, and doing the modular multiplication in the inner loop, in n^3 time. Now! What if there were a magic box you could use? Whenever there are three such numbers in the set, it picks them out; whenever there are none, it just finds any three. You can use that magic box, get the three numbers it picks, check it, and voila, you find your answer immediately, in 1 step instead of n^3. So if a problem is in NP, you need a magic box if the problem is going to be solvable in n^1, n^2, n^3 steps based on n inputs. (They recently showed that Primality-Testing was in P; an n digit number can be factored in n^12 steps. Large, but still polynomial, and better than the exponential-time 2^n.) If a problem is in P, you don't need the magic box to find it in polynomial time. The magic box is the non-deterministic oracle. The polynomial that expresses how hard the problem is, that's the polynomial of polynomial-time. You know "https"? The security of "s" is based on how hard it is to factor two large prime numbers multiplied together, and we know it's in NP (just give me the two numbers, and I can check), but we don't think P=NP, ie we don't think there's an easy way to break all online commerce. (See the RSA algorithm.)
- blantonl 16y ago
  Among other things, we've based electronic commerce on the difficulty of factoring large numbers, which is in NP. If P=NP, then lots of people are going to be very surprised First, thank you for the explanation. However, regarding your quote above, how would electronic commerce change if it was proved that P=NP ? When you say electronic commerce, I think of the process of buying and selling goods. Are you speaking of the analysis of that process?
  - sidww2 16y ago
    If P=NP, then conventional cryptography would be impossible. In particular you would have no public key cryptography so it would not be possible to transmit information securely over an unsecure channel without sharing a some sort of key beforehand. Think of what this will do to online transactions which rely on information like credit card numbers being transmitted securely. I'm sure other areas of the economy would be vastly affected too. The one form of cryptography that would still be possible is quantum cryptography. But if I recall correctly, that requires that two parties already hold some shared secret before communicating. Edit: In addition although it would be possible to detect if someone is eavesdropping over your communication, you still wouldn't have the privilege of being able to communicate securely regardless of whether your message is being recorded. This of course presumes that not only P=NP, but an efficient polynomial time algorithm exists for NP problems i.e. one which is say linear or quadratic or even cubic time.

barrkel 16y ago

To an extreme approximation, problems in P are easy and problems in NP are hard. This is important for e.g. cryptography: its security relies on hard problems staying hard. If it were found that P = NP, it would mean that we would have an easy solution to hard problems. On the other hand, if P != NP, then we could rest assured that the hard problems will stay that way.

carbocation 16y ago
I think that is a bit too extreme of an approximation. What if someone proved that all NP problems could be solved in n * 1000^1000 time? That is in polynomial time (linear, in fact), but completely intractable. Edit: removed Big O notation, since my point here is actually that the constant might be so large that you'd never get to a point where the limiting case would matter. Sorry to set off a firestorm.
- barrkel 16y ago
  I actually removed that point from my comment - that problems in P may be intractable, so it may be academic anyhow. But a way of turning NP-complete problems into problems in P (i.e. P = NP) would hopefully mean that intractable NP problems would be tractable P problems, even if only for relatively small values of n.
  - carbocation 16y ago
    Hopefully true, I agree.
- jules 16y ago
  O(n * c) = O(n), the whole point of the O-notation.
  - carbocation 16y ago
    No. It's only asymptotically equivalent. If the constant is enormous relative to some absolute measure (say, the number of transistors on earth) then O-notation doesn't meaningfully help you.
    - deleted 16y ago
      [deleted]
    - deleted 16y ago
      [deleted]
    - jacobolus 16y ago
      Wrong. O(n * c) = O(n). The definition of O(n) is: f is in O(n) so long as |f(n)| <= M * |n| for some constant M. Likewise, the definition of O(n * c) would be: f is in O(n * c) so long as |f(n)| <= M' * |n * c| for some constant M'. As you can see, any function f which is in O(n * c) is also in O(n), and vice versa. The entire point of complexity classes is to describe asymptotic behavior. If you want to describe something other than asymptotic behavior, find a different tool.
      - carbocation 16y ago
        Despite being correct in the narrow sense, you nevertheless end up being wrong in a broader, more useful sense. I do not disagree with the definition. But you shouldn't rigidly focus on the definition without considering the utility of the notation, and the purpose of the discussion. Big O notation describes the asymptotic behavior of a function when the argument N being passed to it approaches infinity. This is why it is also known as asymptotic notation. Now, since this thread is about practical consequence, there is a severe problem with glibly saying that n * 999^999^999^999^999 will ever remotely resemble n from a practical standpoint. You'll never be able to compute f(1), much less a value of n large enough to be limiting. At any rate, it looks like we both agree that O notation doesn't help you here. My fault for bringing it up.
- jacobolus 16y ago
  > What if someone proved that all NP problems could be solved in O(n) time? You’re quite confused. NP is (at least) a superset of P, and not all problems in P can be solved in linear time (for example, sorting an arbitrarily long list of random numbers). I think you meant something like O(n^(1000^1000))?
  - carbocation 16y ago
    Not confused, though you are correct that we already know that at least some NP cannot be solved in linear time given that NP is a superset of P. I should have phrased things more narrowly. My point is simply to show that even linear-time problems may be computationally intractable.
- nandemo 16y ago
  You could still have used big O notation: "what if some NP-hard problems could be solved in O(n^(1000^1000))?" That is polynomial time so those problems would be in P, but in practice they would be intractable.
blantonl 16y ago
Barrkel: thank you! Edit: so with this in mind, is it safe to say that the NSA's mathematicians are probably the few individuals in the world most interested in this recent development ? Or, are there other types of problems out there that this proof attempts to address? (Commercial etc)
- philwelch 16y ago
  Cryptography is a perverse example where you want to create very hard problems (if not impossible) for others to solve while having some means of keeping the problem easy for yourself and individuals you trust. If we had some easy way to solve problems in NP though, I bet there would be tons of productive applications. I'll quote a friend of mine: "That would transform life on earth, and multiply our technological development rate by a factor unimaginable. There's no way of even estimating what could happen if that problem were solved, unless the polynomial conversion made the problem impossible. ....It would also solve the protein-folding problem and all of the quantum state problems. Money is nifty; immortality and a possible stardrive don't suck. The NP problem is the current barrier to human science. 'There's no way to simulate that' is a constant refrain around here." An interesting way of looking at it is that a valid proof that P != NP would be a kick in humanity's balls comparable to Gödel's incompleteness theorem.
  - eru 16y ago
    Only that most people already expect P != NP. But as you say, P = NP would really make things too easy.
- andreyf 16y ago
  Commercial etc Well, if the opposite had been proven, P = NP, there would be titanic commercial opportunities, but it seems to be the opposite (as most people suspected).
- hc 16y ago
  no, a proof that P!=NP would most likely have no immediate consequences for engineering ("practical") applications to anyone, the people most interested in resolution of P vs NP are complexity theorists and other theoretical computer scientists
deleted 16y ago
[deleted]
_delirium 16y ago
Is there actually much cryptography based on NP-hard problems? Neither integer factorization nor elliptic curves are known to be NP-hard, for example. The first part of your statement is still true (if P=NP, then RSA would be breakable in polynomial time), but I don't think the second part is (proving P!=NP doesn't prove that integer factorization is outside P).
- eru 16y ago
  Cryptography is usually in the intersection between NP and co-NP: NP means a yes-answer is easy to check, co-NP means a no-answer is easy to check. If you are trying to break some encryption you can usually tell quite easily whether you get the right key or not. It would be a major breakthrough (comparable to P=NP) if anyone could show that the intersection of NP and co-NP is equal to NP. Some people tried to make an encryption system out of the knapsack problem (http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack...). It makes a good read about how a promising cryptosystem was broken. Some interesting tid-bit: Even if P != NP, it could still be that most instances of NP-hard problems are easy to solve. (I.e. it's possible that even for NP-hard problems the expected running time is polynomial for all realistic probability distribution of instances. For certain definitions of `realistic'.)

lsb 16y ago

P is the set of all problems that can be verified in time polynomial to the problem space. NP is the set of all problems that can be verified in time polynomial to the problem space with the use of a non-deterministic oracle. Hold that thought. If you have a list of n elements, you can search through the list and check if an element is in that list in n^1 time. If you have a list of n elements, you can check some property on a triplet of numbers in (at worst) n^3 time, looping once for each member of the triplet. I can check that there's a triplet that multiplies to 1337 mod 31337, in a set of n numbers, with three nested loops, and doing the modular multiplication in the inner loop, in n^3 time. Now! What if there were a magic box you could use? Whenever there are three such numbers in the set, it picks them out; whenever there are none, it just finds any three. You can use that magic box, get the three numbers it picks, check it, and voila, you find your answer immediately, in 1 step instead of n^3. So if a problem is in NP, you need a magic box if the problem is going to be solvable in n^1, n^2, n^3 steps based on n inputs. (They recently showed that Primality-Testing was in P; an n digit number can be factored in n^12 steps. Large, but still polynomial, and better than the exponential-time 2^n.) If a problem is in P, you don't need the magic box to find it in polynomial time. The magic box is the non-deterministic oracle. The polynomial that expresses how hard the problem is, that's the polynomial of polynomial-time. You know "https"? The security of "s" is based on how hard it is to factor two large prime numbers multiplied together, and we know it's in NP (just give me the two numbers, and I can check), but we don't think P=NP, ie we don't think there's an easy way to break all online commerce. (See the RSA algorithm.)

blantonl 16y ago
Among other things, we've based electronic commerce on the difficulty of factoring large numbers, which is in NP. If P=NP, then lots of people are going to be very surprised First, thank you for the explanation. However, regarding your quote above, how would electronic commerce change if it was proved that P=NP ? When you say electronic commerce, I think of the process of buying and selling goods. Are you speaking of the analysis of that process?
- sidww2 16y ago
  If P=NP, then conventional cryptography would be impossible. In particular you would have no public key cryptography so it would not be possible to transmit information securely over an unsecure channel without sharing a some sort of key beforehand. Think of what this will do to online transactions which rely on information like credit card numbers being transmitted securely. I'm sure other areas of the economy would be vastly affected too. The one form of cryptography that would still be possible is quantum cryptography. But if I recall correctly, that requires that two parties already hold some shared secret before communicating. Edit: In addition although it would be possible to detect if someone is eavesdropping over your communication, you still wouldn't have the privilege of being able to communicate securely regardless of whether your message is being recorded. This of course presumes that not only P=NP, but an efficient polynomial time algorithm exists for NP problems i.e. one which is say linear or quadratic or even cubic time.