3 ms·
It might be useless for solving NP problems, but that's not the "point" of P=NP per say. P=NP is an intrinsically interesting math problem. And the parent is p
by paulddraper 10y ago
It might be useless for solving NP problems, but that's not the "point" of P=NP per say. P=NP is an intrinsically interesting math problem.
And the parent is pointing out that if P=NP, we already have a construction.
So (if his opinion was presented accurately), Knuth is wrong about a positive proof being non-constructive.
---
I believe there are already known problems whose best solution is O(n^k) for arbitrarily high k. So yeah, naturally not everything will be practically tractable.