News for hackers. Stuff that matters.
Re:Issues in the Proof that P ≠ NP by joe_the_user on Tuesday August 10, 2010 @12:57AM (#1590501)
I haven't looked at the proof in any kind of detail.

But comments by Jame S. Gates etc. raise a question in my mind. Any statical argument that a given phenomena is unlikely is based on the space of phenomena behaving very roughly "communatively" - AB and BA equally likely or at least correlated.

How do you apply that kind of reasoning to a totally arbitrary process of computation, a process which wouldn't necessarily have respect any kind of randomness? It seem like any statistical argument for P=/NP has to have a detailed and direct discussion of how you can escape this problem.

Anyway, that's my crude effort to translate the discussion into my mere math MA understanding...

Re:Issues in the Proof that P ≠ NP by nonce3232321 on Tuesday August 10, 2010 @10:54AM (#1591617)
Probabilistic arguments for deterministic systems are standard practice. Search for Erdős and probabilistic methods to see several examples in combinatorics.

In computation theory many proofs have the tagline "...with probability 1", meaning the author enumerated all desired possibilities and showed their probabilities summed to one. Most people accept this as proof, although it is less preferred, in the way that proof by contradiction is less favored than direct proof.

Re:Issues in the Proof that P ≠ NP by tetha on Tuesday August 10, 2010 @08:28AM (#1591242)
Note, I have not read the paper in detail yet, I just want to explain certain statistical proof techniques which are quite counter-intuitive to me, and maybe help you :)

You can, for example, show the probabilities of certain properties of an algorithm and use these probabilities in order to show the possibility of something existing or the absence of something. Furthermore, you can for example use the expected value of a certain process to demonstrate that solutions with a certain value exist.

For example, if you are able to demonstrate that the expected value of a maximum cut is 5 for a family of graphs, then you can conclude that there are maximum cuts in this family of graphs which have the value of at least 5. There are some with less, and there are some with more, but cuts with weight more than 5 exist.

Or, for example, if you can demonstrate that the probability of a turing machine in a certain class accepting or rejecting after a polynomial time of steps is 0, then it is impossible that this class is identical to P. On the other hand, if it is possible to demonstrate that this probability is not 0 (and thus larger), then we demonstrated that the cut of this class and P is nonempty.

Re:Issues in the Proof that P ≠ NP by Tichy on Tuesday August 10, 2010 @06:34AM (#1591063)
I also don't have high hopes for the statistical angle, in fact I seem to remember that statistical arguments have been around for a long time. But they are not good enough as a proof.