3 ms·

Probably only if P=NP AND if the P algorithms have small polynomials. It's possible that problems which today we only know how to solve with exponential algori

Probably only if P=NP AND if the P algorithms have small polynomials. It's possible that problems which today we only know how to solve with exponential algorithms are in fact solvable with algorithms in O(n^1000000) or whatever, in which case nothing actually changes - for all practical sizes (which is not a lot of sizes at all), the exponential algorithm is actually faster. However, if someone found an O(n^2) algorithm that solves, say, SAT, that would be a major change in our daily lives - there are numerous problems that are completely intractable today that would become quite trivial.

dekhn 3y ago
I'm struggling to see how a proof of P=NP really makes any difference, though- other than psychologically, in the minds of people working on solving problems. It doesn't have any real practical use for people actually building empirically faster implementations of useful algorithms (like SAT, as you mention). I should have been clearer in stating my premise: it appears that determining that P=NP itself would have no real direct impact on any existing real-life problems; in nearly all cases, "faster algorithms that impact life" come from a combination of theoretical computer science discoveries combined with engineering (partly CS engineering, partly hardware engineering). I'd love to find a real counterexample, IE, something in material science, or logistics/optimization, that would make a difference to the world economy. I see CS folks get really excited about this but often times as I poke and pull on the facts, I find that the more theoretical computational complexity gets, the less impact it has on daily activities.
- tsimionescu 3y ago
  I think I see where you're coming from, at least somewhat. Any revolution would come from finding a fast algorithm for an interesting problem, which would also happen to prove P=NP, but that wouldn't be the important part. The algorithm itself would be.
sterlind 3y ago
an O(N^2) algorithm could be useless, if it's a galactic algorithm: https://en.m.wikipedia.org/wiki/Galactic_algorithm https://en.m.wikipedia.org/wiki/Galactic_algorithm conversely, theoretically an O(N^100) algorithm could be practical if it's ~N^2 in practice except on very rare instances. remember big-O is an upper bound.
- tsimionescu 3y ago
  Sure, there are even more caveats. I should note though that big-O is not technically an upper bound on program execution time (worse case scenario), you can use big-O to refer to the best case scenario or the average case. Big-O is a notation for fhe upper bound of a function in general (e.g. f(x) = x^2 + 70x + 9 is in O(x^2)). I think it's reasonable in this kind of case to assume we are speaking about the average-case complexity, though it's true that many think of worse case, taking the upper bound of the upper bound of the number of execution steps.

dekhn 3y ago

I'm struggling to see how a proof of P=NP really makes any difference, though- other than psychologically, in the minds of people working on solving problems. It doesn't have any real practical use for people actually building empirically faster implementations of useful algorithms (like SAT, as you mention). I should have been clearer in stating my premise: it appears that determining that P=NP itself would have no real direct impact on any existing real-life problems; in nearly all cases, "faster algorithms that impact life" come from a combination of theoretical computer science discoveries combined with engineering (partly CS engineering, partly hardware engineering). I'd love to find a real counterexample, IE, something in material science, or logistics/optimization, that would make a difference to the world economy. I see CS folks get really excited about this but often times as I poke and pull on the facts, I find that the more theoretical computational complexity gets, the less impact it has on daily activities.

tsimionescu 3y ago
I think I see where you're coming from, at least somewhat. Any revolution would come from finding a fast algorithm for an interesting problem, which would also happen to prove P=NP, but that wouldn't be the important part. The algorithm itself would be.

sterlind 3y ago

an O(N^2) algorithm could be useless, if it's a galactic algorithm: https://en.m.wikipedia.org/wiki/Galactic_algorithm https://en.m.wikipedia.org/wiki/Galactic_algorithm conversely, theoretically an O(N^100) algorithm could be practical if it's ~N^2 in practice except on very rare instances. remember big-O is an upper bound.

tsimionescu 3y ago
Sure, there are even more caveats. I should note though that big-O is not technically an upper bound on program execution time (worse case scenario), you can use big-O to refer to the best case scenario or the average case. Big-O is a notation for fhe upper bound of a function in general (e.g. f(x) = x^2 + 70x + 9 is in O(x^2)). I think it's reasonable in this kind of case to assume we are speaking about the average-case complexity, though it's true that many think of worse case, taking the upper bound of the upper bound of the number of execution steps.