Publication Details
Title: Algebraic Settings for the Problem
Author: L. Blum, F. Cucker, M. Shub, and S. Smale
Group: ICSI Technical Reports
Date: February 1996
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-96-007.pdf
Overview:
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 Information:
ICSI Technical Report TR-96-007
Bibliographic Reference:
L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic Settings for the Problem. ICSI Technical Report TR-96-007, February 1996
Author: L. Blum, F. Cucker, M. Shub, and S. Smale
Group: ICSI Technical Reports
Date: February 1996
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-96-007.pdf
Overview:
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 Information:
ICSI Technical Report TR-96-007
Bibliographic Reference:
L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic Settings for the Problem. ICSI Technical Report TR-96-007, February 1996