Uri Even-Chen 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. "Completeness" and "Consistency" relate to the relationship between the provability of an expression (syntax) and it's core truthfulness (semantics, or meaning). Since I was not talking about those, these hardly seem relevant.
A theory cannot be either, because a theory is something that needs proof. In other words, using any moderately reasonable tools of proof, a theory can be correct and provable, correct and unprovable or incorrect (we usually do not let go of consistency because that leads to absurds). You will notice, however, that the theory is neither complete NOR consistent. These are measures not meant for theorems, but for logics. Even for logics, the statement above is incorrect. Zero order logic is both consistent AND complete. > 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). This example is way irrelevant. All you really did was trick your way around the definition of what the problem is. > I came to a conclusion that ANY well-defined > function can be computed in polynomial time (in theory). But your proof of this conclusion is incorrectly formed, and thus cannot be validated. I asked you to elaborate your terminology. > 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). I claimed I could prove no such thing. First, I never talked about problems, only about algorithms. Once we agree that an ALGORITHM can be easily categorized on whether or not it belongs to P or to NP, we can use this ability to properly define the P=?NP question. > Any such proof will contain some > uncertainty (or at least, cannot be proved not to contain uncertainty) > and therefore, it can be contradicted. No. Mathematics deal with groups of infinite size on a daily basis, and this has not posed a problem for quite some time. The mere fact that a group has an infinite size does NOT mean it has everything. Trivial example: Is there a number of the form "2n+1", where n is a whole and positive number, that divides by 4? You answer seems to be: Sure there is (or, at least, you cannot prove there isn't). There are an infinite number of such numbers. My answer: No, there isn't. There is, indeed, an infinite quantity of such numbers, but ALL of them divide by 4 with a remainder of either "1" or "3". The fact that there is an infinite number of algorithms does not, in itself, prevent a problem from having a lower bound on the number of operations per element. >> > 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. Ok. Let's take a simple one: Problem: You have a list of numbers in an array. You want to either create a new array, or in the existing array, list the numbers in reverse order to the input one. Proof: No number in the array, with the possible exception of the middle element in the case of an odd sized array, is located at the right place. Any algorithm, by the very constraints posed by the definition of the problem, must be moved. Ergo: The minimal complexity for an algorithm that performs this operation cannot be lower than O(n). QED As a note, since we actually have an algorithm of complexity O(n) that solves the problem, we know that O(n) is not a lower bound, but the actual minimal complexity. You will notice, however, that the actual algorithm was never considered as part of the proof, which is why the proof applies to ANY algorithm. Shachar -- Shachar Shemesh Lingnu Open Source Consulting ltd. Have you backed up today's work? http://www.lingnu.com/backup.html ================================================================= 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]
