- On 3/13/09, Petar Markovic <pera@...> wrote:
> I just got informed of a paper that was recently posted on arXiv which

Dear all,

> supposedly proves P=NP.

> [...] looking for holes [...] perhaps you would like to join in the fun.

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 - Bonjour Nlepatio,Je codirige ton mémoire avec le Dr Celestin Lele. Il faut ajouter son nom et lui donner une copie du memoire pour qu il te fasse part de ses remarques. Vous pouvez regler certaines questions rapidement ensemble.Je repondrai a tes preoccupation plus tard.Etienne Romuald Alomo Temgoua, Ph.D.

2274, Rue Montgomery,

Montreal, QC, H2K 2S1, Canada.Tel. Bureau: +1... Poste: 6706

Tel. Domicile: +1 514 527 6548

**De :**Tomasz Kowalski <tomasz.kowalski@...>**À :**univalg@yahoogroups.com**Envoyé le :**Lundi, 4 Mai 2009, 7h21mn 11s**Objet :**Re: [univalg] P=NPOn 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 - I am sorry for this private message. Please canceled it.Etienne Romuald Alomo Temgoua, Ph.D.

2274, Rue Montgomery,

Montreal, QC, H2K 2S1, Canada.Tel. Bureau: +1... Poste: 6706

Tel. Domicile: +1 514 527 6548

**De :**temgoua etienne <retemgoua@...>**À :**univalg@yahoogroups.com**Envoyé le :**Jeudi, 7 Mai 2009, 10h09mn 26s**Objet :**Re : [univalg] P=NPBonjour Nlepatio,Je codirige ton mémoire avec le Dr Celestin Lele. Il faut ajouter son nom et lui donner une copie du memoire pour qu il te fasse part de ses remarques. Vous pouvez regler certaines questions rapidement ensemble.Je repondrai a tes preoccupation plus tard.Etienne Romuald Alomo Temgoua, Ph.D.

2274, Rue Montgomery,

Montreal, QC, H2K 2S1, Canada.Tel. Bureau: +1... Poste: 6706

Tel. Domicile: +1...

**De :**Tomasz Kowalski <tomasz.kowalski@ anu.edu.au>**À :**univalg@yahoogroups .com**Envoyé le :**Lundi, 4 Mai 2009, 7h21mn 11s**Objet :**Re: [univalg] P=NPOn 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