[tsimionescu]

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.

[Affric]

I 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.

[johnday]

P 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]

Ok. 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]

The 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]

> The question being asked

Where was that question asked?

[tsimionescu]

It 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".