Loading ...
Sorry, an error occurred while loading the content.
 

Re: [univalg] P=NP

Expand Messages
  • Tomasz Kowalski
    ... 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
    Message 1 of 7 , May 4, 2009
      On 3/13/09, Petar Markovic <pera@...> 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
    • temgoua etienne
      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
      Message 2 of 7 , May 7, 2009
        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=NP

        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


      • temgoua etienne
        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.
        Message 3 of 7 , May 7, 2009
          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=NP

          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...  



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

          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



        Your message has been successfully submitted and would be delivered to recipients shortly.