Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!ads.com!sparkyfs.erg.sri.com!vlad
From: vlad@erg.sri.com (beyer)
Newsgroups: comp.theory
Subject: Re: dreams...
Message-ID: <1991Feb22.182340.3566@erg.sri.com>
Date: 22 Feb 91 18:23:40 GMT
References: <9102191402.AA08433@hadar.wisdom.weizmann.ac.il> <18023@cs.utexas.edu> <3002@charon.cwi.nl>
Sender: news@erg.sri.com
Organization: SRI International, Menlo Park, CA
Lines: 37

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


Brought to you by Super Global Mega Corp .com