Comment Re:Use an NP-hard problem (Score 2, Interesting) 608
You've completely misinterpreted my post. The NP complete statement is not referring to the computational requirements of the problem scaling linearly with the complexity of the problem, but scaling with the processing power of the CPU.
This is very different from something like, say, calculating the eigenvalues of very large non-sparse graphs, which is gated primarily on a computer's bus speed. A computer which is 100 times faster than another will still be in the same ballpark assuming reasonably similar chipsets.
There are whole classes of problems which have this quality, many in graph theory for instance. And if a dedicated researcher were to specifically look for such a problem I'm sure they could do much better. That's the point.
This is very different from something like, say, calculating the eigenvalues of very large non-sparse graphs, which is gated primarily on a computer's bus speed. A computer which is 100 times faster than another will still be in the same ballpark assuming reasonably similar chipsets.
There are whole classes of problems which have this quality, many in graph theory for instance. And if a dedicated researcher were to specifically look for such a problem I'm sure they could do much better. That's the point.
