Reasoning
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 n2. 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 1002=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 2n. The number of operations that it will require, for n=100, is 2100. It will take (2100 ÷ 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.
Read more about this topic: Cobham's Thesis
Famous quotes containing the word reasoning:
“Now what I want is facts. Teach these boys and girls nothing but facts. Facts alone are wanted in life. Plant nothing else and root out everything else. You can only form the minds of reasoning animals upon Facts: nothing else will ever be of any service to them.”
—Charles Dickens (1812–1870)
“Reasoning is the pastime of my whole household, and all this reasoning has driven out Reason.”
—Molière [Jean Baptiste Poquelin] (1622–1673)
““Now what I want is, Facts. Teach these boys and girls nothing but Facts. Facts alone are wanted in life. Plant nothing else, and root out everything else. You can only form the minds of reasoning animals upon Facts: nothing else will ever be of service to them.””
—Charles Dickens (1812–1870)