|
NeuroCOLT
Technical Report NC-TR-98-007
Elimination
of Parameters in the Polynomial Hierarchy
Pascal Koiran, ENS Lyon
Keywords:
real polynomial hierarchy; algebraic complexity
Received:
06-MAR-1998
Abstract
Blum, Cucker, Shub and Smale have shown that the problem ``P = NP
?'' has the same answer in all algebraically closed fields of characteristic
0. We generalize this result to the polynomial hierarchy: if it collapses
over an algebraically closed field of characteristic 0, then it must
collapse at the same 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 weaker results hold in positive characteristic.
The present paper updates a report (LIP Research Report 97-37) with
the same title, and in particular includes new results on interactive
protocols and boolean parts.
Download Compressed Postscript
|