Hal Finney:
> I'm not sure if you are disagreeing with either of my statements above,
> that (1) there are no known problems which take exponential time but
> which can be checked in polynomial time, or that (2) if such a problem
> could be found it would prove that P != NP.
Ah, I see the communications glitch was at my end!
You were being precise: NP-complete is not
known (for sure) to be exponentially hard,
so NP-complete problems are not counterexamples
to statement (1)
But maybe (2) doesn't follow.
There must be problems where checking some
negative cases (in the TSP sense) takes more
than polynomial time (maybe doesn't terminate),
but positive answers can be checked in polynomial
time. Those would fit the criteria, but not
be in NP. (Trying to make one up ...)
> As I understand the state of play, factoring into primes is not known
> to be NP-complete, but the contrary is not known, either. Factoring is
> strongly suspected not to be NP-complete but that has not been proven.
> So it is still possible that factoring into primes is just as hard as
> the TSP, although it is thought to be unlikely (it would imply that
> NP = coNP).
Right again, though apparently opinions differ about the unknowns:
<
http://www.math.okstate.edu/~wrightd/crypt/crypt-intro/node23.html>
>> ... It is suspected but not yet known that factoring is NP-complete.
Received on Mon Dec 30 2002 - 21:06:04 PST