> Posted by: "Petar Markovic" pera@...
> I just got informed of a paper that was recently posted on arXiv
> which supposedly proves P=NP. The author is supposed to be a
> professional mathematician with a PhD from SUNY Buffalo (according
> to the K-theorist who told me of it), so it is at least conceivable
> that he got it, though not very likely. Ralph McKenzie, George
> McNulty and I are looking for holes now, but perhaps you would like
> to join in the fun. Here is the link:
>
> http://arxiv.org/abs/0812.1385 <http://arxiv.org/abs/0812.1385>

> Posted by: "Jens Doll" jd@...
> is a hoax. JD

This is contribution 46 to the P=NP question in the enumeration at

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

As such it is the most recent, the oldest being paper 1 in 1986/87, by
Ted Swart at U. Guelph (actually a collection of papers).

Contribution 46 is written in a calm unflappable style not
characteristic of your typical delusional crank. Taking into account
the author's track record in resolving famous open problems, it is way
too complicated to have a high probability of being correct.
Nevertheless out of curiosity I dug around a bit more and learned the
following.

Aslam has two master's degrees, one in computer engineering from some
unnamed IIT in India, the other in computer science from SUNY Buffalo.
His CV at http://madku.com/file/profile/jaslam_1.doc gives his
background as 15+ years in the software industry and 7+ years with
professional services, and says he has "played various leadership roles,
such as Lead Architect, PM and Sr. Analyst in the full SDLC development;
managing various parts of many large IT projects from concept to
implementation." His CV lists no publications.

If K-theorists can be persuaded that such a person is a professional
mathematician with a PhD from SUNY Buffalo, I realize now that I have
been selling the Brooklyn Bridge in all the wrong places: I am going to
start attending K-theory conferences.

This is not to say that Aslam has never published a paper. The 1990
International Conference on Parallel Processing contains a four-page
paper by him, "On Designing Hardware-Efficient Parallel Architectures
for the Class NC," reporting on work that appears to have been
supervised by Sreejit Chakravarty, one of Harry Hunt's collaborators
while Sreejit was an assistant professor at Buffalo (he later moved to
Intel) in the course of Aslam's master's program. The paper outlines a
recursive method for reducing the amount of interconnect hardware
between p(n) parallel processors solving a problem of size n from p(n)^2
(the situation with hypercube and butterfly interconnect topologies) to
n*p(n), which on the face of it seems like a well-motivated and
technically nontrivial result.

Fast forward 16 years. Aslam's method for NP-hard problems seems to
have surfaced first in the form of a Provisional Patent Application to
the US Patent and Trademark Office filed on October 1, 2006. The patent
itself was filed on September 25, 2008. It would make sense that Aslam
would not want to tip his hand before filing the patent, which perhaps
explains why he did not disclose his method prior to uploading his first
version to arXiv on December 7, 2008 under the title "A Permutation
Algebra for Solving NP-Hard Search & Counting Problems." In the course
of the next three of months he uploaded a number of versions, the latest
being version 9 titled "Collapse of the Polynomial Hierarchy: P = NP."
(Scott Aaronson offers something in this attention-grabbing vein at
http://www.scottaaronson.com/writings/phcollapse.pdf, though I'd have
been tempted to include a little history on the origins of the
polynomial hierarchy so as to justify the title "Rise and Fall of the
Polynomial Hierarchy.")

Aslam's current paper seems as well written and clearly explained as his
(rather shorter) 1990 paper. It should be straightforward to translate
his O(n^19) program to something that can be compiled. However given
that 6^19 = 609,359,740,010,496, which in microseconds is 19 years, it
will not be practical to test it on even small examples, as Aslam
himself points out. Any naive method taking time 2^n microseconds will
only be beaten by Aslam's algorithm at n = 135, where both would require
10^27 years.

It will be interesting to see what the patent office decides about his
software patent: this may be USPTO's first exposure to an O(n^19)
algorithm. (It's certainly mine -- the wildly impractical O(n^12)
deterministic (and correct) primality tester from Aslam's three
compatriots is still a far cry from O(n^19), and has come down
considerably since, though not enough to compete in practical
applications with nondeterministic Pratt certificates, which require
time only O(n^2 log^2(n)) to check.)

If Aslam's algorithm does what he claims, this will be a remarkable
example of an amateur coming out of left field with a solution to one of
mathematics' highest ranked open problems. By every indication save the
paper itself, the odds are worse than a hundred to one against. The
paper however must give any skeptic pause. The author's reasonable
presentation style suggests he would quickly acknowledge any serious
difficulties in his proof brought to his attention, which one cannot say
of most crank authors.

That he submitted an algorithm to the patent office that is obviously of
no practical use would suggest he is delusional, were it not for the
fact that he takes care himself to point out how useless it is. This is
why I'm so curious as to USPTO's reaction -- one can imagine their
rejection letter starting out, "We appreciate your candor."

I am looking forward to more specific criticisms of his paper than
simply "it's a hoax."

Vaughan Pratt