Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC840302); site boring.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxj!houxm!whuxlm!harpo!decvax!genrad!teddy!panda!talcott!harvard!seismo!mcvax!boring!paulv
From: paulv@boring.UUCP
Newsgroups: net.math
Subject: Re: Karmarkar algorithm
Message-ID: <6294@boring.UUCP>
Date: Wed, 23-Jan-85 11:27:01 EST
Article-I.D.: boring.6294
Posted: Wed Jan 23 11:27:01 1985
Date-Received: Sun, 27-Jan-85 07:36:10 EST
References: <7700001@hplvle.UUCP> <6285@boring.UUCP> <612@mulga.OZ>
Reply-To: paulv@boring.UUCP (Paul Vitanyi)
Organization: CWI, Amsterdam
Lines: 17
Apparently-To: rnews@mcvax.LOCAL

In article <612@mulga.OZ> bjpt@mulga.OZ (Benjamin Thompson) writes:
>In article <6285@boring.UUCP> paulv@boring.UUCP (Paul Vitanyi) writes:
>>		... 		It was unknown whether LP was as
>>difficult as a large class of problems (NP-Complete Problems) for
>>which only exponential *worst-case* time algorithms are known. When
>>Khachians Ellipsoid Algorithm came along (1979) it was shown
>>that LP is not difficult, in that sense, i.e., the latter algorithm
>>has a polynomial worst-case running time.
>
>
>Khachian's algorithm being polynomial time does *not* mean that LP is not
>an NP-complete problem.  To draw this conclusion, one has to make the
>as-yet *unproven* assumption that NP is not equal to P.
>
>			Ben Thompson, {decvax,vax135}!mulga!bjpt

	If P=NP then every problem in P (and NP) is vacuously NP-complete.