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]
