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:

>> ... It is suspected but not yet known that factoring is NP-complete.

Reply via email to