FtG@rochester.UUCP (01/24/85)
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