10 ms·

I like primers like this but in an attempt to boil it down it misses a sublety - that being that "P" is defined here as a problem a computer can solve "quickly.

I like primers like this but in an attempt to boil it down it misses a sublety - that being that "P" is defined here as a problem a computer can solve "quickly." When really, the class of problems in P are just able to be solved in polynomial time. You could write an algorithm that is O(n^50) that technically is in P, but a computer would take practically forever to solve. Also, there exist problems that are NP hard that cannot be solved in polynomial time and have atrocious worst-case complexity, but their average complexity is quite reasonable and feasible for a machine to calculate. A kind of nitpicky distinction, but this is such a common misunderstanding.

TheRealNGenius 3y ago
[dead]
Laakeri 3y ago
I'm not sure if its really misunderstanding, when in 99% cases it has turned out that if a problem is in P, then it has a polynomial-time algorithm with a quite small exponent.
- Maxatar 3y ago
  I feel like your claim is begging the question. It's certainly not true in principle that most problems in P have a small exponent. There is no shortage of graph related algorithms in P that have absolutely absurd exponents, like on the order of 10^100. It is true that practical decision problems that are in P have small exponents but that's exactly the point being made, namely that problems in P with large exponents are not practical and hence don't get much attention.
  - Laakeri 3y ago
    What are examples of natural graph related problems in P with absurd exponents? I think the reason they don't get attention is not that the algorithms are not practical, but that the problems are not natural. Really, the only examples of such problems I can think of are something like "Finding a clique of size 222222 is in P because we can try all possibilities in n^222222 time".
- jltsiren 3y ago
  As the amount of data grows, exponents that used to be small become large. In many applications, the data grows at least as quickly as computer performance. If the fastest known algorithm is superlinear, today's computers take longer to solve today's problems than yesterday's computers solving yesterday's problems. While O(n^2) time algorithms used to be pretty fast in the 80s, today they are often unusable.
  - Laakeri 3y ago
    I completely agree with you. My point was that the P vs NP distinction matters in practice, but of course also the subquadratic vs quadratic time distinction matters a lot.
ilya_m 3y ago
> Also, there exist problems that are NP hard that cannot be solved in polynomial time and have atrocious worst-case complexity, but their average complexity is quite reasonable and feasible for a machine to calculate. This is an active research topic of trying to characterize worst-case assumptions (i.e., the traditional kind) that imply average-case hardness for some problems, with several recent exciting results. See, for instance, an excellent talk here: https://www.youtube.com/watch?v=aQZEsmpbWE0&t=578s https://www.youtube.com/watch?v=aQZEsmpbWE0&t=578s
- JohnMakin 3y ago
  Great talk thanks for the link!

TheRealNGenius 3y ago

[dead]

Laakeri 3y ago

I'm not sure if its really misunderstanding, when in 99% cases it has turned out that if a problem is in P, then it has a polynomial-time algorithm with a quite small exponent.

Maxatar 3y ago
I feel like your claim is begging the question. It's certainly not true in principle that most problems in P have a small exponent. There is no shortage of graph related algorithms in P that have absolutely absurd exponents, like on the order of 10^100. It is true that practical decision problems that are in P have small exponents but that's exactly the point being made, namely that problems in P with large exponents are not practical and hence don't get much attention.
- Laakeri 3y ago
  What are examples of natural graph related problems in P with absurd exponents? I think the reason they don't get attention is not that the algorithms are not practical, but that the problems are not natural. Really, the only examples of such problems I can think of are something like "Finding a clique of size 222222 is in P because we can try all possibilities in n^222222 time".
jltsiren 3y ago
As the amount of data grows, exponents that used to be small become large. In many applications, the data grows at least as quickly as computer performance. If the fastest known algorithm is superlinear, today's computers take longer to solve today's problems than yesterday's computers solving yesterday's problems. While O(n^2) time algorithms used to be pretty fast in the 80s, today they are often unusable.
- Laakeri 3y ago
  I completely agree with you. My point was that the P vs NP distinction matters in practice, but of course also the subquadratic vs quadratic time distinction matters a lot.

ilya_m 3y ago

> Also, there exist problems that are NP hard that cannot be solved in polynomial time and have atrocious worst-case complexity, but their average complexity is quite reasonable and feasible for a machine to calculate. This is an active research topic of trying to characterize worst-case assumptions (i.e., the traditional kind) that imply average-case hardness for some problems, with several recent exciting results. See, for instance, an excellent talk here: https://www.youtube.com/watch?v=aQZEsmpbWE0&t=578s https://www.youtube.com/watch?v=aQZEsmpbWE0&t=578s

JohnMakin 3y ago
Great talk thanks for the link!