Dr. Z strikes again. Read his 76th opinion, entitled Why P Does Not Equal NP and Why Humans Will Never Prove It by Themselves, and form your own counter-opinion. As usual, reading Zeilberger's opinion won't leave you cold.
Zeilberger writes:
All the problems in, say, Garey and Johnson, are essentially one problem, since they are all trivially equivalent.
Well, I am not sure that I agree that those problems are "trivially" equivalent. "Triviality" is in the eye of the beholder, and maybe one has to be a top notch mathematician like Zeilberger in order to find all of the reductions between NP-complete problems trivial. I admit that I do not find most of them to be trivial at all.
I also find the characterization of the work of complexity theorists as "just proving yet-another reduction theorem" somewhat restrictive.
I am expecting to see some comments on this opinion on the complexity theoretic blogs.
Addendum posted on 15 December 2006: Read Luca Trevisan's thoughtful comments.
Let me also mention another statement of Zeilberger's from opinion 76:
There is no hope, as smart and "creative" as you and your cronies are, that you will be able to prove it by yourselves. Your only hope is to enlist that "simple" mechanical device, that ironically, you computer-scientists, do not use very much, not even for spell-checking!
Now that I have algebraic combinatorialists working near me, I can vouch that they use computers a fair amount in their work---possibly more than many theoretical computer scientists. However, in concurrency theory, people construct and use software tools to make models of computing devices and to analyze their behaviour algorithmically. Readers who have never used such tools might wish to play with Uppaal or HyTech to mention but two such tools.
No comments:
Post a Comment