## 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