On 3/13/09, Petar Markovic <pera@.... yu> wrote:
> I just got informed of a paper that was recently posted on arXiv which
> supposedly proves P=NP.
> [...] looking for holes [...] perhaps you would like to join in the fun.

Dear all,

After reading Petar's post about Aslam's paper, I got some time to
spare and went through it. Since Vaughan Pratt asked for "more
specific criticisms", here is my tuppence worth:

I do not know whether Aslam's method of counting perfect matchings is
correct (it may well be; it worked for two small examples I tried),
but it does not look polynomial.

For an arbitrary bipartite graph, he has to calculate $ER(p)$ (eq.
4.19, p. 16) over all paths in the generating graph $\Gamma(n)$. But
$\Gamma(n)$ comes from $K_{n,n}$, so there are at least $n!$ such
paths.
And from Lemma 4.39, p. 23, it seems there is no way around it.

Tomasz Kowalski