FOM: question for DMNNA panel

[urquhart@urquhart.theory.toronto.edu]

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