3 ms·
There are very obviously algorithms in P which are not "efficient". For example, an algorithm in O(n^10^10^10) is not efficient in any reasonable sense. It is i
by tsimionescu 3y ago
There are very obviously algorithms in P which are not "efficient". For example, an algorithm in O(n^10^10^10) is not efficient in any reasonable sense. It is in fact much much much less efficient than O(e^n) for any n low enough that the whole thing would finish in under a year or so.
In practical terms, the class of efficient algorithms is probably O(n^3) at best, and even then assuming no huge constant factors.
- johnday 3y agoP vs NP is not an "in practical terms" question. It is a theoretical question with theoretical definitions of theoretical terms, including "efficient", which directly corresponds to the class P by definition.
- markusde 3y agoOk. When I say efficient, I mean "produces efficient code on near-term hardware". I understand that complexity theorists have a different definition of "efficient"-- they also have a different definition of "important" too.
- tsimionescu 3y agoThe question being asked was "what would proving P=NP mean for us in practical terms". The fact that mathematicians call all polynomial-time algorithms efficient is irrelevant to this question.
- johnday 3y ago> The question being asked Where was that question asked?
- tsimionescu 3y agoIt wasn't exactly a question, but the thread started by discussing practical implications: > That said, there is definitely potential practical implications for this. Even if it means we can know np problems do not have efficient solutions [emphasis mine] So, this was about efficiency in the practical sense, not some largely useless definition of efficiency by which galactic algorithms are "efficient".
- Affric 3y agoI am not quite the mathematician to find out but I would love to know the relationship between the constant factor and the exponent in matrix multiplication research papers.