96-24: Elimination of Constants from Machines over Algebraically Closed Fields

DIMACS TR: 96-24

Elimination of Constants from Machines over Algebraically Closed Fields

Author: Pascal Koiran

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.

An earlier version of this paper appeared as NeuroCOLT Technical Report 96-43. The present paper contains in particular a new bound for the size of explicit correct test sequences.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-24.ps.gz

DIMACS Home Page