jaw@aurora.UUCP (James A. Woods) (09/15/87)
# "The average mathematician should not forget that
intuition is the final authority." -- J. Barkley Rosser
"There's only one two." -- local TV station slogan
An informative synopsis of P=NP? here is surprising for those
accustomed to the usual style of general-purpose business periodicals.
One would expect something like this to appear in the more outre
New Scientist (hooray for British science writing!), where it might be
by-lined by John Maddox. But the enormity of the question, coupled
with its tight connection to operations research, makes it all
the more important that a general audience is exposed to the art.
The treatment comes complete with mention of revealing Cook/Karp/Levin
history, the role of random oracles, circuit complexity, and the solution
of the old Chomsky grammar chestnut by Neil Immerman. As they say in
the Southern states, "check it out" (of your local public library).
Also entertaining is Steven Johnson's plea for a halt to bogus P=NP
proofs, a cease fire perhaps encouraged by a monetary pot to contain a
$1000 bond for each submission posted before publication, which would then
be forfeited after a bug is found, and thence to the eventual prize
winner, Goedel notwithstanding. It's too bad that a team of "grunt
mathematicians" (*) must still filter the fluff.
Thoughts of anyone other than a Blum or a Karmarkar or a Matyasevich
or an Adelman coming through with a solution may be disturbing to some
workers in the field. Indeed, history has shown repeated lack of faith
with similar assaults [the Bieberbach Conjecture (De Branges), the Poincare
Conjecture (still unresolved), and Fermat's Last Theorem, where episodic
premature announcements in AMS Notices leave no one with even the hope that
a counterexample would fit on a T-shirt.]
As for P=NP, again, refer to the discussion in The Economist for
the week ending 4 September 1987.
-- James A. Woods (ames!jaw)
(*) Term first seen in the seminal paper by DeMillo, Lipton, and Perlis,
CACM, May 1979 -- "Social Processes and Proofs of Theorems and Programs",
well worth your attention for wry commentary and mathematics anecdotes.maiden@sdcsvax.UCSD.EDU (VLSI Layout Project) (09/15/87)
In article <1035@aurora.UUCP> jaw@aurora.UUCP (James A. Woods) writes: >Indeed, history has shown repeated lack of faith >with similar assaults [the Bieberbach Conjecture (De Branges), the Poincare >Conjecture (still unresolved), and Fermat's Last Theorem, where episodic ^^^^^^^^^^^^^^^^ Only unresolved in three dimensions. Resolved for all others.