Elimination of parameters in the polynomial hierarchy

Blum, Cucker, Shub and Smale have shown that the problem "P =NP?" has the s ame answer in all algebraically closed fields of characteristic 0. We gener alize this result to the polynomial hierarchy: if it collapses over an alge braically closed field of characteristic 0, then it must collapse at the sa me level over all algebraically closed fields of characteristic 0. The main ingredient of their proof was a theorem on the elimination of parameters, which we also extend to the polynomial hierarchy. Similar but somewhat weak er results hold in positive characteristic. The present paper updates a technical report (LIP Research Report 97-37) wi th the same title, and in particular includes new results on interactive pr otocols and boolean parts. (C) 1999-Elsevier Science B.V. All rights reserv ed.