3 ms·

Would answering this question have a real impact on daily life?

by dekhn 3y ago

wk_end 3y ago
Depends on the answer.
robot_no_421 3y ago
Yes, in the sense that if P = NP, it would conceptually be a lot easier in theory to break a lot of public key encryption, which are NP hard problems.
lesam 3y ago
If P!=NP, probably nothing changes. If P=NP, a very large class of optimization problems probably become practical to solve, which would be a big win for science and technology generally, to the extent that I think it would be felt in daily life. Edit to add: and also as another commenter mentioned, most existing encryption would likely be much easier to break, which would also be felt.
Almondsetat 3y ago
Yes, if a polynomial algorithm is found for a single NP-complete problem then any other NP problem can be converted and solved polynomially
- travisjungroth 3y ago
  I think this is what’s often missing when this topic is quickly presented. And, it makes the whole thing so much easier to understand. If someone were to prove P = NP by showing how to do it efficiently, that would make many computer problems easier to solve. Even problems like “guessing a password”, and that has obvious implications. If we just knew P = NP because a trusted oracle said so, or someone proved it without showing how to do the conversion, or the conversion was impossibly laborious (a constant 2*100 steps) then that changes much less. If someone proved P ≠ NP that would change the least, since that’s how we operate today. It’s not about getting the answer. It’s about what getting the answer suggests.
- dekhn 3y ago
  But are you sure that woudl actually make any practical difference for any existing problems in the near term?
tsimionescu 3y ago
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.
xyzzy4747 3y ago
The only impact would be the slew of blog articles appearing on Hacker News.

Would answering this question have a real impact on daily life?

by dekhn 3y ago

Would answering this question have a real impact on daily life?

wk_end 3y ago

Depends on the answer.

robot_no_421 3y ago

Yes, in the sense that if P = NP, it would conceptually be a lot easier in theory to break a lot of public key encryption, which are NP hard problems.

lesam 3y ago

If P!=NP, probably nothing changes. If P=NP, a very large class of optimization problems probably become practical to solve, which would be a big win for science and technology generally, to the extent that I think it would be felt in daily life. Edit to add: and also as another commenter mentioned, most existing encryption would likely be much easier to break, which would also be felt.

Almondsetat 3y ago

Yes, if a polynomial algorithm is found for a single NP-complete problem then any other NP problem can be converted and solved polynomially

travisjungroth 3y ago
I think this is what’s often missing when this topic is quickly presented. And, it makes the whole thing so much easier to understand. If someone were to prove P = NP by showing how to do it efficiently, that would make many computer problems easier to solve. Even problems like “guessing a password”, and that has obvious implications. If we just knew P = NP because a trusted oracle said so, or someone proved it without showing how to do the conversion, or the conversion was impossibly laborious (a constant 2*100 steps) then that changes much less. If someone proved P ≠ NP that would change the least, since that’s how we operate today. It’s not about getting the answer. It’s about what getting the answer suggests.
dekhn 3y ago
But are you sure that woudl actually make any practical difference for any existing problems in the near term?

tsimionescu 3y ago

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.

xyzzy4747 3y ago

The only impact would be the slew of blog articles appearing on Hacker News.