% % Ultimate Polynomial Time % ======== ========== ==== % % Gregorio Malajovich % % gregorio@labma.ufrj.br, gregorio@msri.org % % Jan 20, 1999 % % ABSTRACT: The class UP of `ultimate polynomial time' % problems over C is introduced; it contains the class % P of polynomial time problems over C. % The tau-Conjecture for polynomials implies that UP % does not contain the class of non-deterministic % polynomial time problems definable without constants % over C. This latest statement implies that P is not % NP over C. % A notion of `ultimate complexity' of a problem is % suggested. It provides lower bounds for the % complexity of structured problems. % % This is a LaTeX2e file. % \begin{filecontents}{up3.eps} %!PS-Adobe-2.0 EPSF-1.2 %%Creator: MATLAB, The Mathworks, Inc. %%Title: up3.eps %%CreationDate: 01/19/99 18:26:58 %%DocumentNeededFonts: Helvetica %%DocumentProcessColors: Cyan Magenta Yellow Black %%Pages: 1 %%BoundingBox: 192 181 426 589 %%EndComments %%BeginProlog % MathWorks dictionary /MathWorks 160 dict begin % definition operators /bdef {bind def} bind def /ldef {load def} bind def /xdef {exch def} bdef /xstore {exch store} bdef % operator abbreviations /c /clip ldef /cc /concat ldef /cp /closepath ldef /gr /grestore ldef /gs /gsave ldef /mt /moveto ldef /np /newpath ldef /cm /currentmatrix ldef /sm /setmatrix ldef /rc {rectclip} bdef /rf {rectfill} bdef /rm /rmoveto ldef /rl /rlineto ldef /s /show ldef /sc {setcmykcolor} bdef /sr /setrgbcolor ldef /sg /setgray ldef /w /setlinewidth ldef /j /setlinejoin ldef /cap /setlinecap ldef % page state control /pgsv () def /bpage {/pgsv save def} bdef /epage {pgsv restore} bdef /bplot /gsave ldef /eplot {stroke grestore} bdef % orientation switch /portraitMode 0 def /landscapeMode 1 def % coordinate system mappings /dpi2point 0 def % font control /FontSize 0 def /FMS { /FontSize xstore %save size off stack findfont [FontSize 0 0 FontSize neg 0 0] makefont setfont }bdef /reencode { exch dup where {pop load} {pop StandardEncoding} ifelse exch dup 3 1 roll findfont dup length dict begin { 1 index /FID ne {def}{pop pop} ifelse } forall /Encoding exch def currentdict end definefont pop } bdef /isroman { findfont /CharStrings get /Agrave known } bdef /FMSR { 3 1 roll 1 index dup isroman {reencode} {pop pop} ifelse exch FMS } bdef /csm { 1 dpi2point div -1 dpi2point div scale neg translate landscapeMode eq {90 rotate} if } bdef % line types: solid, dotted, dashed, dotdash /SO { [] 0 setdash } bdef /DO { [.5 dpi2point mul 4 dpi2point mul] 0 setdash } bdef /DA { [6 dpi2point mul] 0 setdash } bdef /DD { [.5 dpi2point mul 4 dpi2point mul 6 dpi2point mul 4 dpi2point mul] 0 setdash } bdef % macros for lines and objects /L { lineto stroke } bdef /MP { 3 1 roll moveto 1 sub {rlineto} repeat } bdef /AP { {rlineto} repeat } bdef /PP { closepath eofill } bdef /DP { closepath stroke } bdef /MR { 4 -2 roll moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath } bdef /FR { MR stroke } bdef /PR { MR fill } bdef /L1i { { currentfile picstr readhexstring pop } image } bdef /tMatrix matrix def /MakeOval { newpath tMatrix currentmatrix pop translate scale 0 0 1 0 360 arc tMatrix setmatrix } bdef /FO { MakeOval stroke } bdef /PO { MakeOval fill } bdef /PD { currentlinecap 1 setlinecap 3 1 roll 2 copy moveto lineto stroke setlinecap } bdef /FA { newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arc tMatrix setmatrix stroke } bdef /PA { newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arc closepath tMatrix setmatrix fill } bdef /FAn { newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arcn tMatrix setmatrix stroke } bdef /PAn { newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arcn closepath tMatrix setmatrix fill } bdef /MRR { /vradius xdef /hradius xdef /lry xdef /lrx xdef /uly xdef /ulx xdef newpath tMatrix currentmatrix pop ulx hradius add uly vradius add translate hradius vradius scale 0 0 1 180 270 arc tMatrix setmatrix lrx hradius sub uly vradius add translate hradius vradius scale 0 0 1 270 360 arc tMatrix setmatrix lrx hradius sub lry vradius sub translate hradius vradius scale 0 0 1 0 90 arc tMatrix setmatrix ulx hradius add lry vradius sub translate hradius vradius scale 0 0 1 90 180 arc tMatrix setmatrix closepath } bdef /FRR { MRR stroke } bdef /PRR { MRR fill } bdef /MlrRR { /lry xdef /lrx xdef /uly xdef /ulx xdef /rad lry uly sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 90 270 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 270 90 arc tMatrix setmatrix closepath } bdef /FlrRR { MlrRR stroke } bdef /PlrRR { MlrRR fill } bdef /MtbRR { /lry xdef /lrx xdef /uly xdef /ulx xdef /rad lrx ulx sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 180 360 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 0 180 arc tMatrix setmatrix closepath } bdef /FtbRR { MtbRR stroke } bdef /PtbRR { MtbRR fill } bdef currentdict end def %%EndProlog %%BeginSetup MathWorks begin 0 cap end %%EndSetup %%Page: 1 1 %%BeginPageSetup %%PageBoundingBox: 192 181 426 589 MathWorks begin bpage %%EndPageSetup %%BeginObject: obj1 bplot /dpi2point 12 def portraitMode 0216 7344 csm 2095 273 2801 4896 MR c np 88 dict begin %Colortable dictionary /c0 { 0 0 0 sr} bdef /c1 { 1 1 1 sr} bdef /c2 { 1 0 0 sr} bdef /c3 { 0 1 0 sr} bdef /c4 { 0 0 1 sr} bdef /c5 { 1 1 0 sr} bdef /c6 { 1 0 1 sr} bdef /c7 { 0 1 1 sr} bdef 1 j 1 sg 0 0 6920 5190 PR 6 w -782 677 1355 391 782 -677 2511 4226 4 MP PP -1355 -391 -782 677 1355 391 782 -677 2511 4226 5 MP stroke 0 3160 782 -677 0 -3160 2511 4226 4 MP PP -782 677 0 3160 782 -677 0 -3160 2511 4226 5 MP stroke 0 3160 1355 391 0 -3160 3293 3549 4 MP PP -1355 -391 0 3160 1355 391 0 -3160 3293 3549 5 MP stroke 4 w DO SO 6 w 0 sg 2511 4226 mt 3866 4617 L 3866 4617 mt 4648 3940 L 2511 4226 mt 2511 1066 L 2511 4226 mt 2452 4278 L %%IncludeResource: font Helvetica /Helvetica /ISOLatin1Encoding 120 FMSR 2290 4411 mt (-1) s 2963 4356 mt 2903 4408 L 2811 4542 mt (0) s 3414 4487 mt 3355 4538 L 3262 4672 mt (1) s 3866 4617 mt 3806 4669 L 3714 4802 mt (2) s 3866 4617 mt 3942 4639 L 3975 4759 mt (-1) s 4126 4391 mt 4202 4413 L 4235 4534 mt (0) s 4387 4166 mt 4463 4187 L 4496 4308 mt (1) s 4648 3940 mt 4723 3962 L 4757 4082 mt (2) s 2511 4226 mt 2436 4204 L 2266 4239 mt (-1) s 2511 3775 mt 2436 3753 L 2336 3787 mt (0) s 2511 3323 mt 2436 3301 L 2336 3336 mt (1) s 2511 2872 mt 2436 2850 L 2336 2884 mt (2) s 2511 2420 mt 2436 2398 L 2336 2433 mt (3) s 2511 1969 mt 2436 1947 L 2336 1981 mt (4) s 2511 1518 mt 2436 1496 L 2336 1530 mt (5) s 2511 1066 mt 2436 1044 L 2336 1079 mt (6) s 4679 4917 mt (m1) s 3863 4077 mt (X3) s gs 2511 389 2138 4229 MR c np 3936 3810 mt 3936 3810 L 3936 3810 mt 3936 1101 L gs 3863 2157 147 147 MR c np 36 36 3936 2230 FO gr gs 3863 2608 147 147 MR c np 36 36 3936 2681 FO gr gs 3863 3059 147 147 MR c np 36 36 3936 3132 FO gr gr 3602 4303 mt (X1) s gs 2511 389 2138 4229 MR c np 3675 4035 mt 3675 4035 L 3675 4035 mt 3675 1327 L gs 3602 3285 147 147 MR c np 36 36 3675 3358 FO gr gr 3411 3947 mt (X2) s gs 2511 389 2138 4229 MR c np 3484 3679 mt 3484 3679 L 3484 3679 mt 3484 971 L gs 3411 2478 147 147 MR c np 36 36 3484 2551 FO gr gs 3411 2929 147 147 MR c np 36 36 3484 3002 FO gr gr 3066 5140 mt (m0) s 3150 4173 mt (X0) s gs 2511 389 2138 4229 MR c np 3223 3905 mt 3223 3905 L 3223 3905 mt 3223 1196 L gr 2211 3146 mt -90 rotate (Complex number x) s 90 rotate end eplot %%EndObject epage end showpage %%Trailer %%EOF \end{filecontents} \begin{filecontents}{up.bib} @BOOK{BCSS, AUTHOR = "Lenore Blum and Felipe Cucker and Mike Shub and Steve Smale", TITLE = "Complexity and Real Computation", PUBLISHER = "Springer", YEAR = "1998" } @MISC{LECTURE, AUTHOR = "Steve Smale", TITLE = "Manifestations of Computational Complexity", MONTH = "August", YEAR = "1998", HOWPUBLISHED = "Lecture given at the Introductory Workshop on Foundations of Computational Mathematics and Symbolic Computation in Geometry and Analysis, MSRI", NOTE = "Lecture on video at www.msri.org" } @ARTICLE{Shub-Smale, AUTHOR = "Mike Shub and Steve Smale", TITLE = "On the intractability of {H}ilbert's {N}ullstellensatz and an algebraic version of {$\mathcal P = \mathcal{NP}$}", JOURNAL = "Duke Mathematical J.", VOLUME = "81", PAGES = "47-54", YEAR = "1995" } @ARTICLE{BSS, AUTHOR = "Lenore Blum and Mike Shub and Steve Smale", TITLE = "On a Theory of Computation and Complexity over the Real Numbers: {$\mathcal {NP}$}-completeness, Recursive Functions and Universal Machines", JOURNAL = "Bulletin of the AMS", YEAR = "1989", VOLUME = "21", NUMBER = "1" } @article {KOIRAN97, AUTHOR = {Koiran, Pascal}, TITLE = {A weak version of the {B}lum, {S}hub, and {S}male model}, NOTE = {1st Annual Dagstuhl Seminar on Neural Computing (1994)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {54}, YEAR = {1997}, NUMBER = {1, part 2}, PAGES = {177--189}, } @article {KOIRAN97b, AUTHOR = {Koiran, Pascal}, TITLE = {Elimination of constants from machines over algebraically closed fields}, JOURNAL = {J. Complexity}, FJOURNAL = {Journal of Complexity}, VOLUME = {13}, YEAR = {1997}, NUMBER = {1}, PAGES = {65--82}, } @ARTICLE{MM, AUTHOR = "Gregorio Malajovich and Klaus Meer", TITLE = "On the Structure of {$\mathcal{NP}_{\mathbb C}$}", JOURNAL = "SIAM Journal on Computing", VOLUME = "28", NUMBER = "1", YEAR = "1999" } @article {SmaleXXI, AUTHOR = {Smale, Steve}, TITLE = {Mathematical problems for the next century}, JOURNAL = {Math. Intelligencer}, FJOURNAL = {The Mathematical Intelligencer}, VOLUME = {20}, YEAR = {1998}, NUMBER = {2}, PAGES = {7--15} } @book {GAREY-JOHNSON, AUTHOR = {Garey, Michael R. and Johnson, David S.}, TITLE = {Computers and intractability}, NOTE = {A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences}, PUBLISHER = {W. H. Freeman and Co., San Francisco, Calif.}, YEAR = {1979}, PAGES = {x+338}, } @misc {M99, AUTHOR = "Malajovich, Gregorio", TITLE = "Lower bounds for some decision problems over {$\mathbb C$}", HOWPUBLISHED = "Preprint, MSRI", YEAR = "1999"} \end{filecontents} \documentclass[12pt]{article} \usepackage{amsmath, amssymb, amsthm, amscd} %\usepackage{colordvi} %\usepackage{latexsym} \usepackage{graphics} \newtheorem{theorem} {Theorem} \newtheorem{maintheorem} {Theorem} \newtheorem{lemma} {Lemma} \newtheorem{lowerbound} {Lower bound} \newtheorem{proposition} {Proposition} \newtheorem{corollary} {Corollary} \newtheorem{tauconjecture}{The $\mathbf{\tau}$ Conjecture for Polynomials} \theoremstyle{definition} \newtheorem{example} {Example} \newtheorem{remark} {Remark} \newtheorem{definition} {Definition} \newtheorem{induction} {Induction Hypothesis} \newtheorem{question} {Question} \newtheorem{problem} {Problem} \renewcommand{\themaintheorem}{\Alph{maintheorem}} \renewcommand{\thetauconjecture}{} \newcommand{\binomial}[2] {{\left(\begin{array}{c}#1\\#2\end{array}\right)}} \newcommand{\pnp} {\ensuremath {\mathcal P \ne \mathcal {NP}\ }} \newcommand{\upnp} {\ensuremath {\mathcal {UP} \not \supseteq \mathcal {NP} \cap \mathcal K}\ } \newcommand{\pisnp} {$\mathcal P = \mathcal {NP}$\ } \newcommand{\qalg} {\mathbb Q^{\mathrm{a}}} \newcommand{\qralg} {\mathbb Q^{\mathrm{ra}}} \newcommand{\syl} {\mathrm{Syl}} \newcommand{\res} {\mathrm{Res}} \newcommand{\size} {\mathrm{Size}} \newcommand{\slashpoly} {\ensuremath{_\mathrm{/poly}}} \newcommand{\ppoly} {\ensuremath{\mathcal P\slashpoly}} \newcommand{\hn} {HN} \newcommand{\yes} {^{\mathrm{yes}}} \newcommand{\no} {^{\mathrm{no}}} \newcommand{\nullstellensatz} {\ensuremath{(\hn, \hn \yes)}} \title{Ultimate Polynomial Time} \author{Gregorio Malajovich\footnote{ Departamento de Matem\'atica Aplicada, Universidade Federal do Rio de Janeiro. Caixa Postal 68530, CEP 21945, Rio de Janeiro, RJ, Brasil. e-mail: gregorio@labma.ufrj.br. On leave at MSRI, 1000 Centennial Drive, Berkeley CA 94720-5070. e-mail: gregorio@msri.org }} \date{January 21, 1999} \begin{document} \maketitle \begin{abstract} The class $\mathcal{UP}$ of `ultimate polynomial time' problems over $\mathbb C$ is introduced; it contains the class $\mathcal P$ of polynomial time problems over $\mathbb C$. \par The $\tau$-Conjecture for polynomials implies that $\mathcal{UP}$ does not contain the class of non-deterministic polynomial time problems definable without constants over $\mathbb C$. This latest statement implies that $\mathcal P \ne \mathcal{NP}$ over $\mathbb C$. \par A notion of `ultimate complexity' of a problem is suggested. It provides lower bounds for the complexity of structured problems. \end{abstract} \section{Introduction} \begin{sloppypar} A model of Computation and Complexity over a ring was developed in~\cite{BSS} and ~\cite{BCSS}, generalizing the classical $\mathcal{NP}$-completeness theory~\cite{GAREY-JOHNSON}. Of particular interest is the model of Complexity over the ring $\mathbb C$ of complex numbers. \end{sloppypar} \par In the model of complexity over $\mathbb C$, a machine is allowed to input, to output and to store complex numbers, to compute polynomials and to branch on equality (See the textbook~\cite{BCSS} for background). This model shares some of the features of the classical (Turing) model of computation (There is a discussion in~\cite{MM}). It is known~\cite{KOIRAN97,LECTURE} that the hypothesis $\mathcal {BPP} \not \supseteq \mathcal{NP}$ in the Turing setting implies $\pnp$ over $\mathbb C$. ($\mathcal {BPP}$ stands for Bounded Probability Polynomial Time. If $\mathcal {BPP}$ would happen to contain $\mathcal{NP}$, then there would be polynomial time randomized algorithms for such tasks as factorizing large integers or breaking most modern cryptographic systems). \medskip \par In \cite{Shub-Smale, BCSS, SmaleXXI}, the hypothesis $\pnp$ over the Complex numbers was related to a number-theoretical conjecture. Define a straight-line program as a list \[ s_0 = 1\ ,\ s_1 = x\ ,\ s_2\ , \ \cdots\ , \ s_{\tau} \] where $s_i$ is, for $i\ge 2$, either $s_j+s_k$, $s_j-s_k$ or $s_j s_k$, for some $j, k < i$. Each $s_i$ is thus a polynomial in $x$. The straight-line program is said to {\em compute} the polynomial $s_{\tau}(x)$. \par Given a polynomial $f \in \mathbb Z [x]$, the quantity $\tau(f)$ is defined as the smallest $\tau$ such that there exists a straight-line program $s_0, \cdots, s_{\tau}$ computing $f(x)$. For instance, $\tau(x^{2^n}-1) = 2+n$. Similarly, if $g \in \mathbb Z[x_1, \cdots , x_n]$, then $\tau(g)$ is the minimal length of a straight-line program $s_0=1, s_1=x_1, \cdots, s_n=x_n, s_{n+1}, \cdots, s_{\tau}=g(x)$. \begin{tauconjecture} There is a constant $a > 0$ such that for any univariate polynomial $f \in \mathbb Z[x]$, \[ n(f) < \tau(f)^a \] where $n(f)$ is the number of integer zeros of $f$, without multiplicity. \end{tauconjecture} \medskip \par It is known~\cite{BCSS} that the $\tau$-Conjecture for polynomials implies $\pnp$ over $\mathbb C$. A main step towards this result is the fact that, if the $\tau$-Conjecture is true, then the polynomials \[ p_d(x) = (x-1) (x-2) \cdots (x-d) \] are {\em ultimately hard to compute}. This means that there cannot be constants $a$ and $b$ such that, for any degree $d$, for some non-zero polynomial $f$ (depending on $d$), we would have \[ \tau \left(\ p_d (x) f(x) \ \right) < a \left( \log_2 d \right) ^b \] \par Therefore, all non-zero multiples of $p_d$ are hard to compute, hence the wording ultimately hard. \medskip \par The goal of this paper is to define a new complexity class $\mathcal{UP}$, of {\em ultimate polynomial time} problems. This class will contain $\mathcal P \cap \mathcal K$, where $\mathcal P$ is the class of problems decidable in polynomial time and $\mathcal K$ is the class of problems definable without constants (See~\cite{KOIRAN97b} and Definition~\ref{K} below). Moreover: \begin{theorem} \label{th1} The implications (a) $\Rightarrow$ (b) $\Rightarrow$ (c) $\Rightarrow$ (d) are true: \begin{itemize} \item [(a)] The $\tau$-conjecture for polynomials. \item [(b)] $\forall d$, $p_d$ is ultimately hard to compute. \item [(c)] $\upnp$ over $\mathbb C$. \item [(d)] $\pnp$ over $\mathbb C$. \end{itemize} \end{theorem} \par The implication (a) $\Rightarrow$ (b) $\Rightarrow$ (d) appears in ~\cite{BCSS}, the hypothesis (c) in-between is new. It is at least as likely as the $\tau$-conjecture, while still implying $\pnp$. \par We will also show a $\mathcal{NP}$-hardness result for the class $\mathcal{UP}$: there is a structured problem $\nullstellensatz \in \mathcal{NP} \cap \mathcal K$, such that: \begin{theorem} \label{th2} $\upnp$ over $\mathbb C$ if and only if $\nullstellensatz \not \in \mathcal{UP}$ over $\mathbb C$. \end{theorem} \par The problem $\nullstellensatz$ is precisely the (structured) Hilbert Nullstellensatz, known to be $\mathcal{NP}$-complete over $\mathbb C$~(\cite{BCSS}). \medskip \par This paper was written while the author was visiting Mathematical Sciences Research Institute in Berkeley. The author also wishes to thank Pascal Koiran and Steve Smale for their comments and suggestions. \section{Background and Notations} Recall from $\cite{BCSS}$ that $\mathbb C^{\infty}$ is the disjoint union \[ \mathbb C^{\infty} = \bigsqcup_{i=0, 1, \cdots} \mathbb C^i \] This means that there is a well-defined {\em size} function, \[ \begin{array}{crcl} \size: & \mathbb C^{\infty} & \rightarrow & \mathbb N \\ & x & \mapsto & \size(x) = i \text{\ such that \ } x \in \mathbb C^i \end{array} \] \par A decision problem $X$ is a subset of $\mathbb C^{\infty}$. It is in the class $\mathcal P$ if and only if there is a machine $M$ over $\mathbb C$, that terminates for any input $x$ in time bounded by a polynomial on $\size(x)$, and such that \[ M(x) = 0 \ \Leftrightarrow \ x \in X \] where $M(x)$ is the result of running $M$ with input $x$. Without loss of generality we may assume that $M(x) \in \{ 0;1 \}$. \medskip \par Under some circumstances, it is possible to assume that the machine $M$ above has only coefficients 0 or 1 (This is called a {\em constant-free} machine). However, one may have to replace problem $X$ over $\mathbb C$ by problem $X \cap \mathbb Z$ over $\mathbb Z$, with unit cost. (This is the contents of Propositions~3 and~9 of Chapter~7 of ~\cite{BCSS}). In order to avoid this technical complication and keep the same problem over $\mathbb C$, we will follow another approach to Elimination of Constants. \par This approach was introduced by Koiran in ~\cite{KOIRAN97b}. The idea is to consider only machines for a subclass of problems. This subclass will contain most of the interesting examples, while precluding pathological cases such as $X = \{ \pi \}$. \begin{definition}[Koiran] \label{K} A problem $L$ is said to be {\em definable without constants} if for each input size $n$ there is a formula $F_n$ in the first order theory of $\mathbb C$ such that $0$ and $1$ are the only constants occurring in $F_n$, and for any $x \in \mathbb C^n$, $x \in L$ if and only if $F_n(x)$ is true (there is no restriction on the size of $F_n$. \end{definition} \par For future reference, we quote below Theorem~2 of~\cite{KOIRAN97b}. The original statements of both Definition~\ref{K} and Theorem~\ref {ELIM} are actually more general (for any algebraically closed field of characteristic 0). \begin{theorem}[Koiran] \label{ELIM} Let $L \subseteq K^\infty$ be a problem which is definable without constants. If $L \in \mathcal P$, $L$ can be recognized in polynomial time by a constant-free machine. \end{theorem} \par The class of all the problems definable without constants will be denoted by $\mathcal K$. \medskip \par We will need crucially in the sequel the notion of a {\em structured problem}. A structured problem is a pair $(X, X\yes)$, $X\yes \subseteq X \subseteq \mathbb C^{\infty}$. A non-structured problem $X$ can always be written as the structured problem $(\mathbb C^{\infty}, X)$. The class $\mathcal{UP}$ will be meaningful only as a class of structured problems. But first of all, recall that \begin{definition} A structured problem $(X, X\yes)$ belongs to the class $\mathcal {P}$ if and only if $X \in \mathcal P$ and $X\yes \in \mathcal P$. \end{definition} \begin{definition} A structured problem $(X, X\yes)$ belongs to the class $\mathcal {K}$ if and only if $X \in \mathcal K$ and $X\yes \in \mathcal K$. \end{definition} \begin{definition} A structured problem $(X, X\yes)$ belongs to the class $\mathcal {NP}$ if and only if: \begin{itemize} \item [(1)] The problem $X$ belongs to the class $\mathcal P$. \item [(2)] There is a machine $M$ with input $x,g$ such that \[ x \in X \text{ and } \exists g \in \mathbb C^{\infty} \text { s.t. } M(x,g)=0 \ \Leftrightarrow \ x \in X\yes \] \item [(3)] Furthermore, there is a polynomial $p$ such that, for all $x \in X\yes$, there is $g \in \mathbb C^{\infty}$ such that $M(x,g)=0$ and the running time of $M$ with input $x,g$ is no more than $p(\size(x))$. \end{itemize} \end{definition} \begin{example}\label{ex1} Let $\hn$ be the class of all lists $(m, n, f_1, \cdots,f_m)$ where $f_1, \cdots,$ $f_m$ are polynomials in $n$ variables. Each polynomial $f = \sum f_I x^I$ is represented sparsely by a list of monomials $(S, m_1, \cdots, m_S)$, where each monomial is a list $(f_I, I_1, \cdots, I_n)$. \par An important convention to have in mind: integers appearing in the definition of a problem should be represented in bit representation. In this case, $m, n, S, I_j$ are all lists of zeros and ones. Complex values are represented by one complex number. With this convention, $\hn$ is clearly in the class $\mathcal P$. \par We also define $\hn \yes$ as the subset of polynomial systems in $\hn$ that have a common root over~$\mathbb C$. \par The definition above of the structured problem $\nullstellensatz$ can be translated into first order constant-free formulae over $\mathbb C$. Therefore, $\nullstellensatz \in \mathcal K$. It is also $\mathcal{NP}$-complete over the complex numbers (Theorem~1 in Chapter~5 of ~\cite{BCSS}). \end{example} \begin{example}\label{ex2} Let \begin{eqnarray*} X &=& \left\{ (m,x) \in \mathbb N \times \mathbb C \right\} \\ X\yes &=& \left\{ (m,x) \in X \text{ such that } x \in \{ 1, 2, \cdots, m \} \right\} \\ \end{eqnarray*} with the convention that $m$ is in bit representation, while $x$ is a complex number. Hence, $\size((m,x)) = O(1 + \lceil \log_2 (m) \rceil)$. Then the problem $(X, X\yes)$ is in $\mathcal {NP}$ over $\mathbb C$. The machine $M(x,g)$ can be constructing by guessing the bit decomposition $g_i$ of $x$, and computing $x - \sum g_i 2^i$. \par Again, $(X,X\yes)$ is definable without constants. \end{example} \section{Construction of the class $\mathcal {UP}$} \par In Chapter 7 of~\cite{BCSS}, it is proved that if the problem $(X, X\yes)$ from Example~\ref{ex2} would happen to belong to the class $\mathcal {P}$, then condition (b) in Theorem ~\ref{th1} would be false. Therefore (b) implies \pnp over $\mathbb C$. \medskip \par The class $\mathcal{UP}$ will be constructed by abstracting the same reasoning. The construction relies on some geometric properties of structured problems in $\mathcal P$. The notation that follows will be used in the sequel: \par Let $(X, X\yes)$ be a structured problem with $X \in \mathcal P$. We denote by $X \cap \mathbb C^i$ the set $\{ x \in X: \size(x) = i \}$ of size $i$ instances of the problem. Then we write $\overline {X \cap \mathbb C^i}$ for its Zariski closure over $\mathbb C$. We can define a new object associated to $X$ as: \[ \overline{X} = \bigsqcup_{i=0,1, \cdots} \overline {X \cap \mathbb C^i} \] \par We can think of $\overline{X}$ as the {\em closure} of $X$, indeed it is the smallest `closed' problem containing $X$. Remark that in Examples~\ref{ex1} and~\ref{ex2}, we have respectively $X=\overline{X}$ and $\hn=\overline{\hn}$. \par We can also decompose each Zariski-closed set $\overline {X \cap \mathbb C^i}$ into a finite union of irreducible components (affine varieties). Thus it makes sense to write $\overline{X}$ as the countable union: \[ \overline{X} = \bigcup X_j \] where each $X_j$ is an affine variety lying in some $\mathbb C^s$, where $s = \size (x), x \in X_j$. We can further define: \begin{eqnarray*} X_j\yes &=& X_j \cap X\yes \\ X_j\no &=& X_j \setminus X\yes \end{eqnarray*} \par \begin{figure} \centerline{ \resizebox{4cm}{7cm}{\includegraphics{up3.eps}} \hspace{2cm} \begin{minipage}[b]{4cm} {\sf \footnotesize This is Problem $(X,X\yes)$ from Example~\ref{ex2}, restricted to the inputs $(m_0, m_1, x)$ of size $3$. $X$ is represented by the four (complex !) lines and $X\yes$ by the dots. Each of the complex lines is irreducible, and hence corresponds to a different $X_i$.} \vspace{1cm} \end{minipage} \hspace{2cm} } \caption{\label{fig1} $(X,X\yes)$ from Example~\ref{ex2}} \end{figure} \par (See Figure~\ref{fig1}). Using this notation, \begin{definition}\label{dup} The class $\mathcal{UP}$ is the class of all structured problems $(X, X\yes)$ such that $X \in \mathcal{P}$ and for all $X_i$, there is a non-zero polynomial $f_i \in \mathbb Z[x_1, \cdots, x_{s_i}]$, where $s_i = \size (x)$ for $x \in X_i$, with the following properties: \begin{itemize} \item [(1)] $\tau(f_i)$ is polynomially bounded in $S_i$. \item [(2)] $X_i\yes \subseteq Z(f)$ or $X_i\no \subseteq Z(f)$ \end{itemize} \end{definition} \medskip \par \begin{proposition}\label{pup} $\mathcal P \cap \mathcal K \subseteq \mathcal {UP}$ \end{proposition} \begin{proof}[Proof of Proposition~\ref{pup}] Let $(X,X\yes)$ be in $\mathcal P \cap \mathcal K$. Let $M = M(x)$ be the machine that recognizes $x \in X\yes$ in polynomial time, where the input $x$ is assumed to be in $\overline{X}$. Although it is possible that an $x \in X_i$ is not in $X$, it is still possible to recognize $x \in X\yes$ in polynomial time. Indeed, $X$ is also in $\mathcal P$. The machine $M(x)$ will check $x \in X$ and $x \in X\yes$. \par Now we apply elimination of constants (Theorem~\ref{ELIM}), and choose $M$ to be constant-free. \par The nodes of the machine $M$ are supposed to be numbered. Given an input $x$, the {\em path} followed by input $x$ is the list of nodes traversed during the computation of $M(x)$. \par When the input is restricted to one of the affine varieties $X_i$'s, we can define the canonical path (associated to $X_i$ as the path followed by the generic point of $X_i$. This corresponds to the following procedure: \par At each decision node, at time $T$, branch depends upon an equality $F^T(x) = 0$, where $x$ is the original input. The polynomial $F$ can be computed within the machine running time. In case $F^T(x) = 0$ for all $x \in X_i$, we follow the Yes-path and say that this branching is trivial. \par If not, we follow the no-path and say that this branching is non-trivial. The fact that $X_i$ is a variety is essential here, since it guarantees that only a codimension $\ge 1$ subset of inputs may eventually follow the Yes-path at this time. \par The set of inputs that do NOT follow the canonical path can be described as the zero-set of \[ f_i = \prod F^T \] where the product ranges over the non-trivial branches only. The polynomial $f_i$ can be computed in at most twice the running time of the machine $M$ restricted to $X_i$. By hypothesis, this is polynomial time in the size of $x \in X_i$. \par Since we assumed that $M$ returns only $0$ or $1$, the set of the inputs that follow the canonical path (i.e. $Z(f_i)$) is either all in $X_i\yes$ or all in its complementary $X_i\no$. \par There are now two possibilities. First possibility, $X_i\yes$ has measure zero in $X_i$, and therefore it must be contained in $Z(f_i)$. Second possibility, $X_i\yes$ has non-zero measure, hence it contains the complementary of $Z(f_i)$, and hence $X_i\no$ is a subset of $Z(f_i)$. \end{proof} \section {Proof of the Theorems} \begin{proof}[Proof of Theorem~\ref{th1}] \medskip \ {} \par (a) $\Rightarrow$ (b) is trivial, refer to ~\cite{BCSS} Chapter 7. \medskip \par (b) $\Rightarrow$ (c): Let $(X,X\yes)$ be the problem in Example~\ref{ex2}. Since $X_i\no$ is generic in $X_i$, all inputs in $X_i\yes$ should escape the canonical path. Hence, if $f_d$ is the polynomial that defines the canonical path, $f_d(i) = 0$ for $i=1,2, \cdots, d$. But then it cannot be evaluated in time polylog($d$), by hypothesis (b). Hence, under the assumption (b), the problem $(X,X\yes)$ is not in $\mathcal {UP}$. It does belong to $\mathcal {NP} \cap \mathcal K$, so $\upnp$. \medskip \par (c) $\Rightarrow$ (d) : Using Theorem~\ref{th2}, Condition (c) implies that $\nullstellensatz \not \in \mathcal{UP}$. However, since $\nullstellensatz \in \mathcal K$, Proposition~\ref{pup} implies $\nullstellensatz \not \in \mathcal P$. Hence \pnp over $\mathbb C$. \end{proof} \begin{proof}[Proof of Theorem~\ref{th2}] Let $(X, X\yes) \in \mathcal{NP} \cap \mathcal{K}$ and assume that $\nullstellensatz \in \mathcal{UP}$. We have to show that $(X, X\yes) \in \mathcal{UP}$. \par For each $X_i$, one can embed $(X_i, X_i\yes)$ into some $(\hn_i, \hn_i\yes)$ as follows: \par Let $M = M(x)$ be the deterministic polynomial time machine to recognize $X$, and let $N=N(x,g)$ be the non-deterministic polynomial time machine to recognize $X\yes$. We can assume without loss of generality that $M$ and $N$ are constant-free (Theorem~\ref{ELIM}). \par Let $T$ be the maximum running time of $M$ and $N$ when the input is restricted to $X_i$. Let $\phi(x)$ be the combined Register Equations of machines $M$ and $N$ for time $T$ (Theorem~2 in Chapter~3 of~\cite{BCSS}). Thus, $\phi(x)$ is a system of polynomial equations with integer coefficients and indeterminate coefficients $x_1, x_2, \cdots$. The polynomial system $\phi(x)$ can be constructed in polynomial time from $x$, and the size of $\phi(x)$ is polynomially bounded by the size of $x$. \medskip \par We claim that $\phi(X_i)$ is contained in some $\hn_j$, and that in that case $\phi(X_i\yes) \subseteq \hn_j\yes$ and $\phi(X_i\no) \subseteq \hn_j\no$. \par Indeed, $X_i \subseteq \mathbb C^s$ for some $s$, and $\phi(\mathbb C^s) \subseteq HN_j$ for some $j$. Then $x \in X_i$ belongs to $X\yes$ if and only if the corresponding $\phi(x)$ has a solution over $\mathbb C$. \medskip \par We now distinguish two cases: \par Case 1: $\hn_j\yes$ has measure zero in $\hn_j$. Thus $\hn_j\yes \subseteq Z(\hat f_j)$ for an easy-to-compute polynomial $\hat f_j$. In that case, since $X_i\yes$ gets mapped into $\hn_j\yes$, the composition $f_i = \hat f_j \circ \phi$ gives the polynomial associated to $X_i$. \par Case 2: $\hn_j\no$ has measure zero in $\hn_j$. Thus $\hn_j\no \subseteq Z(\hat f_j)$ for an easy-to-compute polynomial $\hat f_j$. In that case, since $X_i\no$ gets mapped into $\hn_j\no$, $f_i = \hat f_j \circ \phi$ is the polynomial associated to $X_i$. \end{proof} \section{Ultimate Complexity} Let $(Y,Y\yes)$ be a problem over $\mathbb C$, definable without constants and with $Y$ semi-decidable (i.e. $Y$ is the halting set of some machine). The closure $\overline Y$ is well-defined and can be written as a countable union of irreducible varieties $Y_i$. \par For any machine $M$ to solve $(Y,Y\yes)$, one can produce a family of polynomials $f_i$, vanishing on the set of inputs that follow the canonical-path of $M$ restricted to $Y_i$. As in item (2) of Definition~\ref{dup}, we have \[ Y_i\yes \subseteq Z(f_i) \text{\ or\ } Y_i\no \subseteq Z(f_i) \] \par Also, for each input size $s$, one has a finite number of indices $i$ corresponding to components i $Y_i \subseteq \overline Y$ of size-$s$ input. We can thus maximize over those indices $i$: \[ u_M (s) = \max_{i:Y_i \subseteq \mathbb C^{i}} \tau(f_i) \] \par This invariant may be called `ultimate running time', and is a lower bound (up to a constant) for the worst-case running time of $M$. As with ordinary complexity theory, one can define the `ultimate complexity' class of a problem as the class of functions $u: \mathbb N \rightarrow \mathbb R$ such that $\exists M, c>0: \forall x u_M(x) \le c u(x)$ and $M$ recognizes $(Y, Y\yes)$. This provides notions such as `ultimate logarithmic time' or `ultimate exponential time'. \par In~\cite{M99}, a similar construction is used to obtain lower bounds for some specific decision problems. Those problems, however, had a very simple geometric structure (for each `input size', $X\yes$ was a finite set in $\mathbb C$). The motivation of this paper was to extend some of the ideas therein and in Chapter~7 of~\cite{BCSS} to non-codimension-1 problems. \bibliographystyle{plain} \bibliography{up} \end{document}