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 |