Algebraic Settings for the Problem

TitleAlgebraic Settings for the Problem
Publication TypeTechnical Report
Year of Publication1996
AuthorsBlum, L., Cucker F., Shub M., & Smale S.
Other Numbers1017

When complexity theory is studied over an arbitrary unordered field K, the classical theory is recaptured with K = Z2. The fundamental result that the Hilbert Nullstellensatz as a decision problem is NP-complete over K allows us to reformulate and investigate complexity questions within an algebraic framework and to develop transfer principles for complexity theory. Here we show that over algebraically closed fields K of characteristic 0 the fundamental problem "P does not equal NP?" has a single answer that depends on the tractability of the Hilbert Nullstellensatz over the complex number. A key component of the proof is the Witness Theorem enabling the elimination of transcendental constants in polynomial time.

Bibliographic Notes

ICSI Technical Report TR-96-007

Abbreviated Authors

L. Blum, F. Cucker, M. Shub, and S. Smale

ICSI Publication Type

Technical Report