Very simply some problems are impossible to solve in a reasonable amount of time or at all; these problems may looks simple, but their complexity can explode.

Very simply some problems are impossible to solve in a reasonable amount of time or at all; these problems may looks simple, but their complexity can explode. For instance chess is relatively easy to program where as go is quite a bit more difficult. --------------------------------------- Here's a very good quote from wikipedia that might make it clearer: The thesis is widely considered to be a good rule of thumb for real-life problems. Typical input lengths that users and programmers are interested in are between 100 and 1,000,000, approximately. Consider an input length of n=100 and a polynomial algorithm whose running time is n^2. This is a typical running time for a polynomial algorithm. (See the "Objections" section for a discussion of atypical running times.) The number of steps that it will require, for n=100, is 100^2=10000. A typical CPU will be able to do approximately 109 operations per second (this is extremely simplified). So this algorithm will finish on the order of (10000 ÷109) = .00001 seconds. A running time of .00001 seconds is reasonable, and that's why this is called a practical algorithm. The same algorithm with an input length of 1,000,000 will take on the order of 17 minutes, which is also a reasonable time for most (non-real-time) applications. Meanwhile, an algorithm that runs in exponential time might have a running time of 2^n. The number of operations that it will require, for n=100, is 2^100. It will take (2^100 ÷ 109) ≈ 1.3×1021 seconds, which is (1.3×1021 ÷ 31556926) ≈ 4.1×1013 years. The largest problem this algorithm could solve in a day would have n=46, which seems very small. http://en.wikipedia.org/wiki/Cobham%27s_thesis http://en.wikipedia.org/wiki/Cobham%27s_thesis