Wednesday, August 11, 2010

My objection to the P!=NP proof

There's a lot of genuine interest in the attempt to proove P!=NP. I was interested enough to read the abstract and then I got worried. I kept reading and was quite puzzled by the general approach of the paper. My understanding was sufficient to develop a simple objection to the proof. Luckily, I could find a statement in the proof that admits a simple counter-example.

1. My general concern is the use of Markov properties to prove some deterministic properties. It may be possible, but quite hard. In general, independence is a very strong property and it is hard to say anything about the lack of independence. Therefore, the reliance on the large size of connected variables isn’t sufficient.

2. Following (1), the following statement is plain wrong and easy to verify:
Chapter 2, pg 28. “When the size of the smallest irreducible interactions is O(n), then we need O(c^n) parameters where c > 1 .”

Before giving an example, I rephrase it for completness:

When the size of the smallest irreducible interactions [in a markov network with N variables], is n, then we need O(c^n) parameters [to specify the distribution] where c > 1.

Here’s a counter example. Consider a markov network, of N binary variables. Each variable can be 0 or 1 with probability 1/2. All variables are independent so far. Now, add a constrain that all variables can not be 1 at the same time.

This simple constrain requires ALL variables to be connected, but the description is compact.
In this simple case, the apparent complexity is high, but the distribution is quite simple.