On Wed, 25 Apr 2007 16:27:23 +0300 "Uri Even-Chen" <[EMAIL PROTECTED]> wrote:
> 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*. For each _specific_ input. This version won't work for a class of problems and you can't say that you can build a table of answers since you still have the problem of choice, which taken straight forward is exponential (since the number of options grows exponentially with n). > 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? > Like I said, there are two O(1) algorithms, at least one of which is correct, but the choice between them can be hard, and you are interested in the choice, i.e in the correct solution, not whether it can be given easily once you know it for the _specific_ problem. > 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). > Like I said, you try to prove your point by answering a completely question than the one you posed. For a given problem there is a algorithm that gives the correct answer in O(1), you just don't know which one to choose. For a given class of problems (like whether an input integer is divisible by 4) the solution may or may not be O(1) since the one algorithm doesn't work any more, you need to chose one or the other and the question of choice is the issue and depends of the specific input. > 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] > ================================================================= 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]
