🚀 go-pugleaf

In article <1992Nov19.102822.1@zodiac.rutgers.edu>, I said:
| Yes.  Programs in class P are defined as those for which, for any input of
| length n, we can prove they halt after taking no more than p(n) steps, where
| p is some polynomial.

This is poorly stated.  Whether a program is in P or not is a fact, whether we
can prove if or not.  A program is in P if there exists a polynomial p such
that, for any input of length n, the program will, in fact, halt in most p(n)
steps.  If proving that things were or were not in P were trivial, then the
question of whether P equals NP would be trivial, too:  Because, say, 3-SAT
is complete for NP, if we could prove 3-SAT was in P, we'd know P=NP; if we
could prove 3-SAT was NOT in P, then P!=NP.  As it is, we simply don't know.

(And, yes, there are all sorts of philosophical - and mathematical! - com-
plexities to the question of what "actually does halt" means!  Since it is
known that there are oracles relative to which one can prove P=NP, and others
relative to which one can prove P!=NP, in a sense there are "plausible worlds"
(or very slightly more general notions of computation) in which P=NP, and
other "plausible worlds" in which P!=NP.)
							-- Jerry