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.