24/03/10 01:06:26.84 86TMEkfZ.net
>>294
Now, if we assume that the proposition does not hold, then for every problem, there exists a problem a whose algorithm does not match the class of the problem, and is of a smaller class.
At this time, it is possible to create a program A that generates problem a infinitely.
Let there be a program X that creates problems infinitely, and let r(X) be the ratio of the total problems solved by it.
In the case of A, even if we take n as large as possible with time being ∞^n, r(A) converges to 0.
Let P be the set of all true proof problems, and let p be the set of all computational problems, then P ⊃ p.
To solve a computational problem means to demonstrate the following two points:
(1) Decide whether there is a better algorithm than brute force search, and if it exists, demonstrate that it is the best; if not, demonstrate its non-existence.
(2) If it exists, verify whether a solution exists using that algorithm and specifically output the value. If it does not exist, verify the existence of a solution through brute force search.