By the way, it's very easy to prove that for any specific decision problem, *there is* an algorithm who returns a correct answer in O(1). Consider these two algorithms: "always return 0" and "always return 1". At least one of them returns a correct answer for *any input*. But if a general problem is considered to be hard, it must contain a subset of "really hard problems", which cannot be calculated in O(1) by *any* algorithm. But at least one of my algorithms returns a correct answer for each of those "really hard problems". Then a subset of "really hard problems" can never be proved to exist. And if a set contains only "easy" problems, then how hard can it be?
This can even be extended to the halting problem. For any specific algorithm it is possible to return the correct answer in O(1), if a correct answer exists. If it is proved not to be computable in O(1), then a definite answer doesn't exist (any definite answer will lead to a contradiction). Uri. ================================================================= To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
