This reminds me an interesting question cryptographers deal with nowadays:
what is a secure cryptographic hash function. In short (assuming you all know what a hash function is), a cryptographic hash function is such that it is hard to find collisions (i.e., x and x' s.t. h(x) = h(x')), second pre-image (given x finding x' s.t. h(x)=h(x')) and pre-images (given y, find x s.t. h(x)=y). The reason we have problems is that collisions must exist, and if a and b is a collision than print(a,b) is a polynomial time algorithm which outputs the collision. Of course, this is dubious, because for any given hash function we might know the specific algorithm. For more information about that, lock at http://eprint.iacr.org/2006/281 In any case, there are infinite (Aleph zero) number of polynomial algorithms, but there is (Aleph one) languages. Actually, the only reason this is not a proof that P \neq NP is because the size of NP is Aleph zero. So indeed there are sufficiently many algorithms, but the question is whether the number of languages the algorithms identify is infinite (please note that two algorithms may identify the same language). As for O(1) for all algorithms - there are many such languages. For example, determining whether an input string is of the form a^n||b^n requires reading the string (so the running time of any algorithm that solves it is at least O(n)). There are even problems were you can prove that you need extra memory of logarithmic size (see the connectivity problem). And finally, the question whether P=NP does not necessarily require the theory complexity to be complete. And given the definitions its quite consistent (as long as polynomials are consistent). Orr. On 4/24/07, Uri Even-Chen <[EMAIL PROTECTED]> wrote:
On 4/24/07, Shachar Shemesh <[EMAIL PROTECTED]> wrote: > Uri Even-Chen wrote: > > Hi people, > > > > Recently I checked some problems in mathematics, computer science and > > physics. For a long time I had the intuition that the P vs NP Problem > > is an undecidable problem. I think the only conclusion we have is > > that there is no solution, I don't think P and NP are mathematically > > well defined. > How so? For any given algorithm, the questions "is the algorithm > polinomially bounded" and "is the algorithm non-deterministicly > polinomially bounded" can be, fairly easilly, answered. That satisfy the > group theory requirement for a "well behaved definition" for both P and NP. > > Where is that flaw in the definition? No theory can be both complete and consistent. Every question we ask affects the answer. For example, the question "is the number 10 prime?" depends on whether 10 is a binary number or a decimal number (or any base-n number). I came to a conclusion that ANY well-defined function can be computed in polynomial time (in theory). There are infinitely many algorithms. It is not possible to prove that any specific problem is not polynomial (unless it's not computable and therefore not well defined). Any such proof will contain some uncertainty (or at least, cannot be proved not to contain uncertainty) and therefore, it can be contradicted. > > You can see my proof here: > > http://www.speedy.net/uri/blog/?p=19 > Your terminology seems off. You appear to be using "O(n)" in a way that > is inconsistent with the way it is defined in computer science, yet you > provide no definition of your own for what it means. This is, of course, > unless I totally mis-read your proof. I'm referring to the general case, whether any specific problem is not in O(1). No specific problem can be proved not to be in O(1) for all algorithms. I also wrote more articles, for example a proof that the speed of light is not constant (or more generally speaking, that deterministic constants don't exist). It means that there is no theoretical limit to the speed any particle can travel in spacetime. But I don't know whether or not it applies to humans. The term "human" itself is intuitive and I don't think it can be defined physically in any deterministic way which is not inconsistent. http://www.speedy.net/uri/blog/?cat=3 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]
-- 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])
