Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site rochester.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxj!houxm!whuxlm!harpo!decvax!genrad!teddy!panda!talcott!harvard!seismo!rochester!FtG
From: FtG@rochester.UUCP
Newsgroups: net.math
Subject: Karmarkar and NP-Complete
Message-ID: <5679@rochester.UUCP>
Date: Thu, 24-Jan-85 07:54:29 EST
Article-I.D.: rocheste.5679
Posted: Thu Jan 24 07:54:29 1985
Date-Received: Sun, 27-Jan-85 07:24:18 EST
Sender: FtG@rochester.UUCP
Organization: U. of Rochester, CS Dept.
Lines: 21

From: FtG

Some basic facts:

1)  If P = NP then all but TWO Poly time languages are NP/P complete
under poly time reductions:  Namely the empty and universal sets.

2)  Most people nowadays (although there are famous exceptions) use
Log space reductions in their definitions of completeness.  Hence
if Log space <> P and P = NP then ONLY the Poly time complete problems
(which includes all NP-complete problems under Log space reductions (which
in turn includes all known NP-complete problems)) would be Poly time
complete.

Hence it is possible that P = NP but LP is not P or NP complete under
Log space reductions.

Partially uneducated prediction:  LP will be shown to be sub-poly space
and therefore not likely to even be Poly time complete.

FtGone