FOM: question for DMNNA panel
urquhart@urquhart.theory.toronto.edu
urquhart at urquhart.theory.toronto.edu
Mon Jun 12 12:37:03 EDT 2000
I agree with Dave Marker that the panel discussion in Urbana
was most interesting and provocative.
Avi Wigderson's talk was excellent too. The "axiom" or
assumption that Dave refers to should, I think, be the
"factoring is hard" axiom, not the "multiplication is hard" axiom.
The security of the RSA cryptosystem, currently used for a lot
of net-based commercial transactions, rests on this (empirically) well-supported
assumption. Unfortunately, there is no solid theoretical
background for it.
The multiplication question to which
Avi Wigderson referred is the question whether multiplication really
is harder than addition in a computational sense. This must
be one of the oldest questions in computational complexity theory.
It's stated right at the beginning of Alan Cobham's seminal article
of 1964:
The subject of my talk is perhaps most directly indicated
by simply asking two questions: first, is it harder to
multiply than to add? and second, why?
("The intrinsic computational difficulty of functions",
LMPS 1964 proceedings)
It's amazing that this question is still open after over thirty years
of intensive research
Alasdair Urquhart
More information about the FOM
mailing list