FOM: question for DMNNA panel

[Stephen G Simpson]

Dave Marker Mon, 12 Jun 2000 10:12:07 -0500 (CDT) asked how
Widgerson's assumption ``factoring is hard'' (i.e., ``there is no
polynomial time algorithm for factoring positive integers'') fits into
the subject of the ASL 2000 panel discussion on

       Does Mathematics Need New Axioms?

My comment would be that the DMNNA panel discussion had a very
different focus, namely the role of axioms going beyond ZFC,
especially large cardinal axioms.  Such axioms have a very different
status, in that they are well known to be independent of ZFC.  By
contrast, ``factoring is hard'' is not known (and not likely) to be
independent of ZFC or even PA or, more relevantly, Bounded Arithmetic.
It is simply an important open problem in mathematics/computer
science.  If I may be permitted a Buss-like prediction, I predict that
``factoring is hard'' will be proved (more likely) or disproved within
the next 50 years, using no special assumptions.

To my mind, the ongoing use of the assumption ``factoring is hard'' by
computer scientists, which Widgerson exposited masterfully in his
talk, is in the same spirit as how a number theorist might give a talk
on results that have been proved under the assumption of the Extended
Riemann Hypothesis.  In both cases, the assumption is extremely
fruitful and seems likely to be true, but its proof presents a well
known stumbling block, so in the meantime we go ahead and use it.

-- Steve