Re: P≠NP Experimental Evidence

[Torben Ægidius Mogensen]

Mustafa Algebra <algebra...@gmail.com> writes:

> Is there any experimental evidence for P≠NP? I tried doing experiments
> with simple programs I wrote and it yielded P≠NP (NP took less time to
> compute than P). This may be taking more of a scientific approach than
> a mathematical one though...

You can't verify P≠NP or P=NP experimentally, as Patricia said. There
is anecdotal evidence that P≠NP, as noone has been able (in spite of
many attempts) to show a provably P-time implementation of an NP-hard
problem. It is not hard to construct a program that provably runs in P
if P=NP, but even if you make tests that show that the running time for
this increases polynomially for all the inputs sizes tested, this
doesn't help you, as the curve might bend just above the sizes you
tested. And since this is about worst-case running times, it might be
that your tests only involve the easy cases. Even if P=NP, it might be
that the running time of the optimal program might grow exponentially up
to problem sizes equal to the number of atoms in the universe, though
the asymptotic runtime is polynomial. And no experiment will ever
reveal this.

In a way, it is easier to prove P=NP (if this is true) than P≠NP (if
this is true): You just have to make a program solving an NP-hard
problem and prove that its worst-case running time is polynomial. To
prove P≠NP, you must prove that no such program exist.

Torben