On 10/10/2010 8:07 PM, Norbert Nemec wrote:
"Impossible to solve" is often used synonymous to "exponentially hard to solve" meaning, as the problem size (e.g. size of finite memory) grows as N, the cost for solution grows as exp(N). Of course, the actual cost of an actual problem always depends on the pre-factor, but experience shows that exponentially hard problems are typically only solvable for trivially small problems.
That's a fair observation. Cheers Justin Johansson