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:
“Education is a necessity, it helps to understand life. Like that compagnero in Cuba who talked about politics, back when they were on strike. He knew many things, that hijo de puta, and he unraveled the most confusing situations in a marvelous way. You could see each point in front of you on the line of his reasoning like rinsed laundry set up to dry; he explained things to you so clearly that you could grasp it like a good hunk of bread with your hand.”
—Jacques Roumain (1907–1945)
““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)
“For this is one of the ancientest laws among them; that no man shall be blamed for reasoning in the maintenance of his own religion.”
—Sir Thomas More (1478–1535)