[johnday]

> Even a P=NP result doesn't tell us that NP problems have efficient solutions.

Yes it does. That is literally exactly what it means. The class P is the class of problems which are considered theoretically "tractable"/"efficiently solvable"/"feasibly solvable" (Cobham-Edmonds thesis). Hence, if NP=P, then that same definition extends to all problems in NP.

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

That's not Cobham-Edmonds thesis. The assertion is that problems are feasible _only if_ they are in P, not _if and only if_ they are in P.

[johnday]

Sorry, but no. Edmonds clearly maps "efficiently-solvable problems" onto the notion of P in a complete way, not only as a subset of P.