|
NeuroCOLT
Technical Report NC-TR-96-043
Elimination
of Constants from Machines over Algebraically Closed Fields
Pascal
Koiran
Ecole Normale Superieure de Lyon
France
Abstract
Let $\k$ be an algebraically closed field of characteristic
0. We show that constants can be removed efficiently from any machine
over $\k$ solving a problem which is definable without constants.
This gives a new proof of the transfer theorem of Blum, Cucker, Shub
& Smale for the problem $\p \stackrel{?}{=}\np$. We have similar
results in positive characteristic for non-uniform complexity classes.
We also construct explicit and correct test sequences (in the sense
of Heintz and Schnorr) for the class of polynomials which are easy
to compute.
Download Compressed
Postscript
|