10 ms·

The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means th

The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this may help a academic researcher in CompSci, but it probably doesn't change much for most programmers.

nerdponx 9y ago
Beyond crypto, problems like the traveling salesman would also be solvable in polynomial time.
- Govindae 9y ago
  Well... The traveling salesman decision problem, not the general case. The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum. What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.
  - hnaccy 9y ago
    If you can solve the decision TSP in polytime you can solve the optimization case in polytime.
    - hexomancer 9y ago
      How? edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version. I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed: First we do a binary search on `L` (the length of the tour- input to the decision version) so we can find the optimal L within a factor of epsilon (maybe this epsilon is the flaw? But I don't think that is the case.) Now we pick an edge and increase its weight to infinity. Now we do the binary search again on the new graph. If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution. By doing the same process on all the edges we can find the optimal solution. As I said there must be a flaw in the above algorithm but I can't find it.
      - mihaild 9y ago
        First, use binary search to find answer. Then, remove edges one-by-one if removing this edge will not destroy all remaining path with shortest length, until your graph is reduced to a single cycle.
        hexomancer 9y ago
        Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity because I think the TSP problem is defined only on complete graphs) But as I have mentioned in my comment I feel like this solution is flawed.
        zmonx 9y ago
        You can without loss of generality assume that the weights are integers (if they are rational, you can multiply all weights so that they become integral). Hence, you can use bisection to compute the actual optimum, not involving epsilon at all.
      - mihaild 9y ago
        Epsilon isn't a problem, as TSP is NP-complete even for integer weights. Your solution needs some modification for case where we have multiple optimal cycles (as you will find edges that are included in at least one cycle). I don't think there is anything wrong with optimization been reducible to decision - it's quite common method both in theory and in practice.
        hexomancer 9y ago
        I didn't say there is anything wrong with reducing the optimization to decision in general. But I feel this specific application to the TSP problem may be flawed. (for the reasons i mentioned before. i.e wikipedia being very specific about the decision version) For another resource see: https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en https://www.ibm.com/developerworks/community/blogs/jfp/entry... note: I am not implying that the above source is reputable. But it does hint that the solution to this problem probably is not this trivial.
vanjoe 9y ago
I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.
- DonbunEf7 9y ago
  On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.
  - vanjoe 9y ago
    I'm pretty far out of my area of expertise, so I'll take your word for it. Could an an algorithm be correct, but not proven correct, or is it defined as a heuristic at that point?
    - hood_syntax 9y ago
      Godel's incompleteness theorem would seem to imply that is possible unless I'm misinterpreting it. I have a rather elementary understanding.
      - adam-fn 9y ago
        The Collatz conjecture ( https://xkcd.com/710/ https://xkcd.com/710/ ) may well be an example here.
    - Chinjut 9y ago
      An algorithm could certainly be correct (in the sense of always giving the correct result) without being proven to do so (or even without any such proof existing, in some particular formal system). You are not wrong about that.
quickthrower2 9y ago
What about large constants?
legulere 9y ago
Would it present a problem for cryptography though? Quadratic algorithms are seen as already slow, cubic algorithms as unbearable garbage you best try to avoid if your data size is not tiny. And this completely ignores constant factors that can play a big role. Homomorphic encryption for instance fails to be usable just on a huge constant factor.
- Ar-Curunir 9y ago
  Yes, it would. The adversary in cryptography is assumed to be worst-case evil; it'll do whatever it can to break your algorithm, as long as it's performing a polynomial amount of computation. Remember, you're not just fighting your friendly neighborhood hacker, but possibly entire nation-states.
  - PeterisP 9y ago
    You can easily have crypto that can't be broken with all the resources and time in the observable universe even if it's "just" polynomial with a sufficiently high coefficient.
    - kevincox 9y ago
      Yes, but it becomes significantly more expensive. It might work but it is a huge difference in cost tradeoffs.

nerdponx 9y ago

Beyond crypto, problems like the traveling salesman would also be solvable in polynomial time.

Govindae 9y ago
Well... The traveling salesman decision problem, not the general case. The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum. What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.
- hnaccy 9y ago
  If you can solve the decision TSP in polytime you can solve the optimization case in polytime.
  - hexomancer 9y ago
    How? edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version. I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed: First we do a binary search on `L` (the length of the tour- input to the decision version) so we can find the optimal L within a factor of epsilon (maybe this epsilon is the flaw? But I don't think that is the case.) Now we pick an edge and increase its weight to infinity. Now we do the binary search again on the new graph. If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution. By doing the same process on all the edges we can find the optimal solution. As I said there must be a flaw in the above algorithm but I can't find it.
    - mihaild 9y ago
      First, use binary search to find answer. Then, remove edges one-by-one if removing this edge will not destroy all remaining path with shortest length, until your graph is reduced to a single cycle.
      - hexomancer 9y ago
        Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity because I think the TSP problem is defined only on complete graphs) But as I have mentioned in my comment I feel like this solution is flawed.
        zmonx 9y ago
        You can without loss of generality assume that the weights are integers (if they are rational, you can multiply all weights so that they become integral). Hence, you can use bisection to compute the actual optimum, not involving epsilon at all.
    - mihaild 9y ago
      Epsilon isn't a problem, as TSP is NP-complete even for integer weights. Your solution needs some modification for case where we have multiple optimal cycles (as you will find edges that are included in at least one cycle). I don't think there is anything wrong with optimization been reducible to decision - it's quite common method both in theory and in practice.
      - hexomancer 9y ago
        I didn't say there is anything wrong with reducing the optimization to decision in general. But I feel this specific application to the TSP problem may be flawed. (for the reasons i mentioned before. i.e wikipedia being very specific about the decision version) For another resource see: https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en https://www.ibm.com/developerworks/community/blogs/jfp/entry... note: I am not implying that the above source is reputable. But it does hint that the solution to this problem probably is not this trivial.

vanjoe 9y ago

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

DonbunEf7 9y ago
On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.
- vanjoe 9y ago
  I'm pretty far out of my area of expertise, so I'll take your word for it. Could an an algorithm be correct, but not proven correct, or is it defined as a heuristic at that point?
  - hood_syntax 9y ago
    Godel's incompleteness theorem would seem to imply that is possible unless I'm misinterpreting it. I have a rather elementary understanding.
    - adam-fn 9y ago
      The Collatz conjecture ( https://xkcd.com/710/ https://xkcd.com/710/ ) may well be an example here.
  - Chinjut 9y ago
    An algorithm could certainly be correct (in the sense of always giving the correct result) without being proven to do so (or even without any such proof existing, in some particular formal system). You are not wrong about that.

quickthrower2 9y ago

What about large constants?

legulere 9y ago

Would it present a problem for cryptography though? Quadratic algorithms are seen as already slow, cubic algorithms as unbearable garbage you best try to avoid if your data size is not tiny. And this completely ignores constant factors that can play a big role. Homomorphic encryption for instance fails to be usable just on a huge constant factor.

Ar-Curunir 9y ago
Yes, it would. The adversary in cryptography is assumed to be worst-case evil; it'll do whatever it can to break your algorithm, as long as it's performing a polynomial amount of computation. Remember, you're not just fighting your friendly neighborhood hacker, but possibly entire nation-states.
- PeterisP 9y ago
  You can easily have crypto that can't be broken with all the resources and time in the observable universe even if it's "just" polynomial with a sufficiently high coefficient.
  - kevincox 9y ago
    Yes, but it becomes significantly more expensive. It might work but it is a huge difference in cost tradeoffs.