On 4/24/07, Nadav Har'El <[EMAIL PROTECTED]> wrote:
You said that "I came to a conclusion that ANY well-defined function can be computed in polynomial time (in theory).", but this is NOT true on a deterministic Turing Machine. For various algorithms, it is very easy to prove that they are *NOT* in P, i.e., there cannot be any polynomial-time algorithm. Such are algorithms which require exponential computation time (I'm sure you can think of some).
Actually, courtesy of Galois we know functions which are well defined, that can be easily verified and not computed efficiently - the roots of general polynomials over R of degree > 4. Specifically, to incorporate this problem to the Turing model, you must assume that the machine can work with real numbers (over bits), which is not the case. But when you define a "Real-number turing machine" you get that for this machine P is not equal to NP. However, as Nadav said, the question P = NP? is defined over a turing machine with bits as the building blocks (the values on the infinite string). Orr. -- Orr Dunkelman, [EMAIL PROTECTED] "Any human thing supposed to be complete, must for that reason infallibly be faulty" -- Herman Melville, Moby Dick. GPG fingerprint: C2D5 C6D6 9A24 9A95 C5B3 2023 6CAB 4A7C B73F D0AA (This key will never sign Emails, only other PGP keys. The key corresponds to [EMAIL PROTECTED])
