harel@WISDOM.WEIZMANN.AC.IL (David Harel) (02/21/91)
"I have a dream ..." (Martin Luther King) I thought it would be nice to share with you a dream I had last night. (Some people dream a lot; I don't. Some probably dream about their work; I have never.) The dream featured Roger Penrose, who had just proved that P=NP. He kept saying that he had done some work on approximate solutions to the timetable problem (or the traveling salesman problem -- I can't remember which one it was), and, in thinking them over a few days ago, a polynomial-time solution suddenly came to him. All dreams seem to have a frustrating part to them, and this was no exception. There were two. One was my repeated, frantic attempts to try to get Penrose to explain the solution to me. No luck! What a pity. Try to imagine a story in the New York Times science section, describing the solution to the P vs. NP problem as having been revealed to the author in a dream... The other frustration, involved trying to convince all kinds of strange people who kept showing up in my office at all hours, demanding that I explain what more is there to complexity theory, and what will all the great talents in this area do, now that not only has their main open problem been resolved, but it has been resolved in such a way as to render equivalent so many interestingly different-looking complexity classes. I remember having only very feeble and unconvincing answers for them, and kept mumbling all kinds of junk... That's when the dream ended. No, there was no screaming or cold sweat or anything like that, but I sure hope P is not equal to NP. David Harel
turpin@cs.utexas.edu (Russell Turpin) (02/21/91)
----- In describing a dream, Mr Harel said something that struck me as expressing an attitude fundamentally against progress. In article <9102191402.AA08433@hadar.wisdom.weizmann.ac.il> David Harel <harel%wisdom.weizmann.ac.il@VM1.NoDak.EDU> writes: > ... No, there was no screaming or cold sweat or anything like > that, but I sure hope P is not equal to NP. It would be much better if P=NP. Any proof of this would undoubtedly reveal new ways to better solve important problems that are currently intractable except on relatively small sets. > The other frustration, involved trying to convince all kinds > of strange people who kept showing up in my office at all hours, > demanding that I explain what more is there to complexity theory, > and what will all the great talents in this area do, now that > not only has their main open problem been resolved, but it has > been resolved in such a way as to render equivalent so many > interestingly different-looking complexity classes. ... These are smart people. They would quickly find other important problems on which to focus. Indeed, this would be an important benefit of proving P=NP: it would free up all these bright people to work on problems that remain unsolved. All practical research is inherently the kind of work that when it succeeds well, it destroys the very field in which the work was done. There are many fewer people now working on cures or preventions for smallpox than there were fifty years ago. The workers fifty years ago succeeded well, and put themselves out of work. (Or at least, they put themselves out of *that* work. I have no doubt that most went on to other useful work in medicine.) A simple cure for AIDS would eliminate many current research jobs. Should we for that reason hope this disease has no simple cure? Everyone doing practical research should keep in mind that it is their goal to make sure that their current job is one for which there is no need in ten years. Russell
vlad@erg.sri.com (beyer) (02/23/91)
In article <3002@charon.cwi.nl> lambert@cwi.nl (Lambert Meertens) writes: >In article <18023@cs.utexas.edu> turpin@cs.utexas.edu (Russell Turpin) writes: >) > , but I sure hope P is not equal to NP. >) >) It would be much better if P=NP. Any proof of this would >) undoubtedly reveal new ways to better solve important problems >) that are currently intractable except on relatively small sets. > >What if we find an order THETA(n^794948115) algorithm? And what about the >possibility of a non-constructive proof of P=NP, that is, one that proceeds >by reducing the assumption that none of those algorithms "out there" in the >ocean of polynomial algorithms solves say 3SAT to an absurdity without >giving any clue in the process as to which one might do the trick? > >Actually, if the P=NP? question will ever be settled, of the two possible >verdicts: a proof that P != NP, and a proof that P = NP, the non-construc- >tive version of the latter seems to me -- for intuitive reasons that I >cannot justify -- the more plausible possibility; it's what I would put my >money on if I were into betting. > >-- > >--Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl If your intuition is correct, wouldn't we have a lot of fun looking for a "constructive" proof (i.e., an ACTUAL polynomial algorithm for solving, say, Travelling Salesman problem), once the non-constructive proof of its existence is found? Even if the exponent will turn out to be huge, say 4884587. That way, we could spend the next 100 years gradually lowering it to n^4884586, then to n^4884585, then to n^4884584*log n, etc. :-) Vlad
kono@csl.sony.co.jp (Shinji Kono) (02/23/91)
In article <3002@charon.cwi.nl> , lambert@cwi.nl (Lambert Meertens) writes >Actually, if the P=NP? question will ever be settled, of the two possible >verdicts: a proof that P != NP, and a proof that P = NP or it may one of the independent problem, like continuum hypothesis. -------- Shinji Kono, E-Mail: kono@csl.sony.co.jp, nifty: MAF00476 $@2OLn??<#(J Sony Computer Science Laboratory, Inc.
kondoh@harl86.harl.hitachi.co.jp (Hidetaka KONDOH) (03/12/91)
In article <1971@virgo.csl.sony.co.jp> kono@csl.sony.co.jp (Shinji Kono) writes: >>In article <3002@charon.cwi.nl> >> , lambert@cwi.nl (Lambert Meertens) writes >>>Actually, if the P=NP? question will ever be settled, of the two possible >>>verdicts: a proof that P != NP, and a proof that P = NP >> >>or it may one of the independent problem, like continuum hypothesis. No, I think it is not the case, since with 2nd-order formulation of the mathematical induction (i.e. \forall X [X(0) & \forall v [X(v) -> X(s(v))] -> \forall v X(v)] ), the axiom system of Peano arithmetic is categorical (having unique model except for non-standard models, which do not interpret \in (membership-predicate symbol) as the membership relation), and "P = NP" problem would be able to be formulated in this 2nd-order Peano arithmetic, so that problem must be either true or false in its unique standard model. (In the case of the continuum hypothesis, there are standard models of ZF set theory in some of which the hypothesis comes true and in others it is given falsity.) Of course, due to the Incompleteness theorem of Godel, there are many sentences which are independent of the categorical 2nd-order Peano arithmetic, but in the unique standard model of the theory can give true or false decisively to each of those sentences. -- -- Hidetaka KONDOH (kondoh@harl.hitachi.co.jp) Advanced Research Laboratory Hitachi, Ltd. Voice: +81-492-96-6111/6112 (Ext. 6328) Hatoyama, Saitama 350-03 Fax: +81-492-96-6005 JAPAN
kondoh@harl86.harl.hitachi.co.jp (Hidetaka KONDOH) (03/12/91)
In article <1721@harl86.harl.hitachi.co.jp> kondoh@harl86.harl.hitachi.co.jp (Hidetaka KONDOH) writes:
%%"P = NP" problem would be able to be formulated in this 2nd-order
%%Peano arithmetic, so that problem must be either true or false in
%%its unique standard model.
%%
And this is definite (not arbitrary, but we don't know whether
it is true or false now, of cource :-))
--
Hidetaka KONDOH (kondoh@harl.hitachi.co.jp) Advanced Research Laboratory
Hitachi, Ltd.
Voice: +81-492-96-6111/6112 (Ext. 6328) Hatoyama, Saitama 350-03
Fax: +81-492-96-6005 JAPAN