Algebraic Settings for the Problem
Title | Algebraic Settings for the Problem |
Publication Type | Technical Report |
Year of Publication | 1996 |
Authors | Blum, L., Cucker F., Shub M., & Smale S. |
Other Numbers | 1017 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-96-007.pdf |
Bibliographic Notes | ICSI Technical Report TR-96-007 |
Abbreviated Authors | L. Blum, F. Cucker, M. Shub, and S. Smale |
ICSI Publication Type | Technical Report |