# Ultimate Polynomial Time

## 1 Introduction

A model of Computation and Complexity over a ring was developed in  and , generalizing the classical $`𝒩𝒫`$-completeness theory . Of particular interest is the model of Complexity over the ring $``$ of complex numbers.

In the model of complexity over $``$, a machine is allowed to input, to output and to store complex numbers, to compute polynomials and to branch on equality (See the textbook  for background). This model shares some of the features of the classical (Turing) model of computation (There is a discussion in ). It is known  that the hypothesis $`𝒫𝒫𝒩𝒫`$ in the Turing setting implies $`𝒫𝒩𝒫`$ over $``$. ($`𝒫𝒫`$ stands for Bounded Probability Polynomial Time. If $`𝒫𝒫`$ would happen to contain $`𝒩𝒫`$, then there would be polynomial time randomized algorithms for such tasks as factorizing large integers or breaking most modern cryptographic systems).

In , the hypothesis $`𝒫𝒩𝒫`$ 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,\mathrm{},s_\tau $$

where $`s_i`$ is, for $`i2`$, either $`s_j+s_k`$, $`s_js_k`$ or $`s_js_k`$, for some $`j,k<i`$. Each $`s_i`$ is thus a polynomial in $`x`$. The straight-line program is said to compute the polynomial $`s_\tau (x)`$.

Given a polynomial $`f[x]`$, the quantity $`\tau (f)`$ is defined as the smallest $`\tau `$ such that there exists a straight-line program $`s_0,\mathrm{},s_\tau `$ computing $`f(x)`$. For instance, $`\tau (x^{2^n}1)=2+n`$. Similarly, if $`g[x_1,\mathrm{},x_n]`$, then $`\tau (g)`$ is the minimal length of a straight-line program $`s_0=1,s_1=x_1,\mathrm{},s_n=x_n,s_{n+1},\mathrm{},s_\tau =g(x)`$.

###### The $`\tau `$ Conjecture for Polynomials .

There is a constant $`a>0`$ such that for any univariate polynomial $`f[x]`$,

$$n(f)<\tau (f)^a$$

where $`n(f)`$ is the number of integer zeros of $`f`$, without multiplicity.

It is known  that the $`\tau `$-Conjecture for polynomials implies $`𝒫𝒩𝒫`$ over $``$. A main step towards this result is the fact that, if the $`\tau `$-Conjecture is true, then the polynomials

$$p_d(x)=(x1)(x2)\mathrm{}(xd)$$

are 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(\mathrm{log}_2d\right)^b$$

Therefore, all non-zero multiples of $`p_d`$ are hard to compute, hence the wording ultimately hard.

The goal of this paper is to define a new complexity class $`𝒰𝒫`$, of ultimate polynomial time problems. This class will contain $`𝒫𝒦`$, where $`𝒫`$ is the class of problems decidable in polynomial time and $`𝒦`$ is the class of problems definable without constants (See  and Definition 1 below). Moreover:

###### Theorem 1.

The implications (a) $``$ (b) $``$ (c) $``$ (d) are true:

* The $`\tau `$-conjecture for polynomials.
* $`d`$, $`p_d`$ is ultimately hard to compute.
* $`𝒰𝒫𝒩𝒫𝒦`$ over $``$.
* $`𝒫𝒩𝒫`$ over $``$.

The implication (a) $``$ (b) $``$ (d) appears in , the hypothesis (c) in-between is new. It is at least as likely as the $`\tau `$-conjecture, while still implying $`𝒫𝒩𝒫`$.

We will also show a $`𝒩𝒫`$-hardness result for the class $`𝒰𝒫`$: there is a structured problem $`(HN,HN^{\mathrm{yes}})𝒩𝒫𝒦`$, such that:

###### Theorem 2.

$`𝒰𝒫𝒩𝒫𝒦`$ over $``$ if and only if $`(HN,HN^{\mathrm{yes}})𝒰𝒫`$ over $``$.

The problem $`(HN,HN^{\mathrm{yes}})`$ is precisely the (structured) Hilbert Nullstellensatz, known to be $`𝒩𝒫`$-complete over $``$ ().

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.

## 2 Background and Notations

Recall from  that $`^{\mathrm{}}`$ is the disjoint union

$$^{\mathrm{}}=\underset{i=0,1,\mathrm{}}{}^i$$

This means that there is a well-defined size function,

$$\begin{array}{cccc}\mathrm{Size}:& \hfill ^{\mathrm{}}& & \hfill \\ & \hfill x& & \mathrm{Size}(x)=i\text{ such that }x^i\hfill \end{array}$$

A decision problem $`X`$ is a subset of $`^{\mathrm{}}`$. It is in the class $`𝒫`$ if and only if there is a machine $`M`$ over $``$, that terminates for any input $`x`$ in time bounded by a polynomial on $`\mathrm{Size}(x)`$, and such that

$$M(x)=0xX$$

where $`M(x)`$ is the result of running $`M`$ with input $`x`$. Without loss of generality we may assume that $`M(x)\{0;1\}`$.

Under some circumstances, it is possible to assume that the machine $`M`$ above has only coefficients 0 or 1 (This is called a constant-free machine). However, one may have to replace problem $`X`$ over $``$ by problem $`X`$ over $``$, with unit cost. (This is the contents of Propositions 3 and 9 of Chapter 7 of ). In order to avoid this technical complication and keep the same problem over $``$, we will follow another approach to Elimination of Constants.

This approach was introduced by Koiran in . 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 \}`$.

###### Definition 1 (Koiran).

A problem $`L`$ is said to be definable without constants if for each input size $`n`$ there is a formula $`F_n`$ in the first order theory of $``$ such that $`0`$ and $`1`$ are the only constants occurring in $`F_n`$, and for any $`x^n`$, $`xL`$ if and only if $`F_n(x)`$ is true (there is no restriction on the size of $`F_n`$.

For future reference, we quote below Theorem 2 of . The original statements of both Definition 1 and Theorem 3 are actually more general (for any algebraically closed field of characteristic 0).

###### Theorem 3 (Koiran).

Let $`LK^{\mathrm{}}`$ be a problem which is definable without constants. If $`L𝒫`$, $`L`$ can be recognized in polynomial time by a constant-free machine.

The class of all the problems definable without constants will be denoted by $`𝒦`$.

We will need crucially in the sequel the notion of a structured problem. A structured problem is a pair $`(X,X^{\mathrm{yes}})`$, $`X^{\mathrm{yes}}X^{\mathrm{}}`$. A non-structured problem $`X`$ can always be written as the structured problem $`(^{\mathrm{}},X)`$. The class $`𝒰𝒫`$ will be meaningful only as a class of structured problems. But first of all, recall that

###### Definition 2.

A structured problem $`(X,X^{\mathrm{yes}})`$ belongs to the class $`𝒫`$ if and only if $`X𝒫`$ and $`X^{\mathrm{yes}}𝒫`$.

###### Definition 3.

A structured problem $`(X,X^{\mathrm{yes}})`$ belongs to the class $`𝒦`$ if and only if $`X𝒦`$ and $`X^{\mathrm{yes}}𝒦`$.

###### Definition 4.

A structured problem $`(X,X^{\mathrm{yes}})`$ belongs to the class $`𝒩𝒫`$ if and only if:

* The problem $`X`$ belongs to the class $`𝒫`$.
* There is a machine $`M`$ with input $`x,g`$ such that

$$xX\text{ and }g^{\mathrm{}}\text{ s.t. }M(x,g)=0xX^{\mathrm{yes}}$$
* Furthermore, there is a polynomial $`p`$ such that, for all $`xX^{\mathrm{yes}}`$, there is $`g^{\mathrm{}}`$ such that $`M(x,g)=0`$ and the running time of $`M`$ with input $`x,g`$ is no more than $`p(\mathrm{Size}(x))`$.

###### Example 1.

Let $`HN`$ be the class of all lists $`(m,n,f_1,\mathrm{},f_m)`$ where $`f_1,\mathrm{},`$ $`f_m`$ are polynomials in $`n`$ variables. Each polynomial $`f=f_Ix^I`$ is represented sparsely by a list of monomials $`(S,m_1,\mathrm{},m_S)`$, where each monomial is a list $`(f_I,I_1,\mathrm{},I_n)`$.

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 $`𝒫`$.

We also define $`HN^{\mathrm{yes}}`$ as the subset of polynomial systems in $`HN`$ that have a common root over $``$.

The definition above of the structured problem $`(HN,HN^{\mathrm{yes}})`$ can be translated into first order constant-free formulae over $``$. Therefore, $`(HN,HN^{\mathrm{yes}})𝒦`$. It is also $`𝒩𝒫`$-complete over the complex numbers (Theorem 1 in Chapter 5 of ).

###### Example 2.

Let

$`X`$ $`=`$ $`\left\{(m,x)\times \right\}`$   
$`X^{\mathrm{yes}}`$ $`=`$ $`\left\{(m,x)X\text{ such that }x\{1,2,\mathrm{},m\}\right\}`$   
with the convention that $`m`$ is in bit representation, while $`x`$ is a complex number. Hence, $`\mathrm{Size}((m,x))=O(1+\mathrm{log}_2(m))`$. Then the problem $`(X,X^{\mathrm{yes}})`$ is in $`𝒩𝒫`$ over $``$. The machine $`M(x,g)`$ can be constructing by guessing the bit decomposition $`g_i`$ of $`x`$, and computing $`xg_i2^i`$.

Again, $`(X,X^{\mathrm{yes}})`$ is definable without constants.

## 3 Construction of the class $`𝒰𝒫`$

In Chapter 7 of , it is proved that if the problem $`(X,X^{\mathrm{yes}})`$ from Example 2 would happen to belong to the class $`𝒫`$, then condition (b) in Theorem 1 would be false. Therefore (b) implies $`𝒫𝒩𝒫`$over $``$.

The class $`𝒰𝒫`$ will be constructed by abstracting the same reasoning. The construction relies on some geometric properties of structured problems in $`𝒫`$. The notation that follows will be used in the sequel:

Let $`(X,X^{\mathrm{yes}})`$ be a structured problem with $`X𝒫`$. We denote by $`X^i`$ the set $`\{xX:\mathrm{Size}(x)=i\}`$ of size $`i`$ instances of the problem. Then we write $`\overline{X^i}`$ for its Zariski closure over $``$. We can define a new object associated to $`X`$ as:

$$\overline{X}=\underset{i=0,1,\mathrm{}}{}\overline{X^i}$$

We can think of $`\overline{X}`$ as the closure of $`X`$, indeed it is the smallest ‘closed’ problem containing $`X`$. Remark that in Examples 1 and 2, we have respectively $`X=\overline{X}`$ and $`HN=\overline{HN}`$.

We can also decompose each Zariski-closed set $`\overline{X^i}`$ into a finite union of irreducible components (affine varieties). Thus it makes sense to write $`\overline{X}`$ as the countable union:

$$\overline{X}=X_j$$

where each $`X_j`$ is an affine variety lying in some $`^s`$, where $`s=\mathrm{Size}(x),xX_j`$. We can further define:

$`X_j^{\mathrm{yes}}`$ $`=`$ $`X_jX^{\mathrm{yes}}`$   
$`X_j^{\mathrm{no}}`$ $`=`$ $`X_jX^{\mathrm{yes}}`$   
(See Figure 1). Using this notation,

###### Definition 5.

The class $`𝒰𝒫`$ is the class of all structured problems $`(X,X^{\mathrm{yes}})`$ such that $`X𝒫`$ and for all $`X_i`$, there is a non-zero polynomial $`f_i[x_1,\mathrm{},x_{s_i}]`$, where $`s_i=\mathrm{Size}(x)`$ for $`xX_i`$, with the following properties:

* $`\tau (f_i)`$ is polynomially bounded in $`S_i`$.
* $`X_i^{\mathrm{yes}}Z(f)`$ or $`X_i^{\mathrm{no}}Z(f)`$

###### Proposition 1.

$`𝒫𝒦𝒰𝒫`$

###### Proof of Proposition 1.

Let $`(X,X^{\mathrm{yes}})`$ be in $`𝒫𝒦`$. Let $`M=M(x)`$ be the machine that recognizes $`xX^{\mathrm{yes}}`$ in polynomial time, where the input $`x`$ is assumed to be in $`\overline{X}`$. Although it is possible that an $`xX_i`$ is not in $`X`$, it is still possible to recognize $`xX^{\mathrm{yes}}`$ in polynomial time. Indeed, $`X`$ is also in $`𝒫`$. The machine $`M(x)`$ will check $`xX`$ and $`xX^{\mathrm{yes}}`$.

Now we apply elimination of constants (Theorem 3), and choose $`M`$ to be constant-free.

The nodes of the machine $`M`$ are supposed to be numbered. Given an input $`x`$, the path followed by input $`x`$ is the list of nodes traversed during the computation of $`M(x)`$.

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:

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 $`xX_i`$, we follow the Yes-path and say that this branching is trivial.

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 $`1`$ subset of inputs may eventually follow the Yes-path at this time.

The set of inputs that do NOT follow the canonical path can be described as the zero-set of

$$f_i=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 $`xX_i`$.

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^{\mathrm{yes}}`$ or all in its complementary $`X_i^{\mathrm{no}}`$.

There are now two possibilities. First possibility, $`X_i^{\mathrm{yes}}`$ has measure zero in $`X_i`$, and therefore it must be contained in $`Z(f_i)`$. Second possibility, $`X_i^{\mathrm{yes}}`$ has non-zero measure, hence it contains the complementary of $`Z(f_i)`$, and hence $`X_i^{\mathrm{no}}`$ is a subset of $`Z(f_i)`$. ∎

## 4 Proof of the Theorems

###### Proof of Theorem 1.

(a) $``$ (b) is trivial, refer to  Chapter 7.

(b) $``$ (c): Let $`(X,X^{\mathrm{yes}})`$ be the problem in Example 2. Since $`X_i^{\mathrm{no}}`$ is generic in $`X_i`$, all inputs in $`X_i^{\mathrm{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,\mathrm{},d`$. But then it cannot be evaluated in time polylog($`d`$), by hypothesis (b). Hence, under the assumption (b), the problem $`(X,X^{\mathrm{yes}})`$ is not in $`𝒰𝒫`$. It does belong to $`𝒩𝒫𝒦`$, so $`𝒰𝒫𝒩𝒫𝒦`$.

(c) $``$ (d) : Using Theorem 2, Condition (c) implies that $`(HN,HN^{\mathrm{yes}})𝒰𝒫`$. However, since $`(HN,HN^{\mathrm{yes}})𝒦`$, Proposition 1 implies $`(HN,HN^{\mathrm{yes}})𝒫`$. Hence $`𝒫𝒩𝒫`$over $``$. ∎

###### Proof of Theorem 2.

Let $`(X,X^{\mathrm{yes}})𝒩𝒫𝒦`$ and assume that $`(HN,HN^{\mathrm{yes}})𝒰𝒫`$. We have to show that $`(X,X^{\mathrm{yes}})𝒰𝒫`$.

For each $`X_i`$, one can embed $`(X_i,X_i^{\mathrm{yes}})`$ into some $`(HN_i,HN_i^{\mathrm{yes}})`$ as follows:

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^{\mathrm{yes}}`$. We can assume without loss of generality that $`M`$ and $`N`$ are constant-free (Theorem 3).

Let $`T`$ be the maximum running time of $`M`$ and $`N`$ when the input is restricted to $`X_i`$. Let $`\varphi (x)`$ be the combined Register Equations of machines $`M`$ and $`N`$ for time $`T`$ (Theorem 2 in Chapter 3 of ). Thus, $`\varphi (x)`$ is a system of polynomial equations with integer coefficients and indeterminate coefficients $`x_1,x_2,\mathrm{}`$. The polynomial system $`\varphi (x)`$ can be constructed in polynomial time from $`x`$, and the size of $`\varphi (x)`$ is polynomially bounded by the size of $`x`$.

We claim that $`\varphi (X_i)`$ is contained in some $`HN_j`$, and that in that case $`\varphi (X_i^{\mathrm{yes}})HN_j^{\mathrm{yes}}`$ and $`\varphi (X_i^{\mathrm{no}})HN_j^{\mathrm{no}}`$.

Indeed, $`X_i^s`$ for some $`s`$, and $`\varphi (^s)HN_j`$ for some $`j`$. Then $`xX_i`$ belongs to $`X^{\mathrm{yes}}`$ if and only if the corresponding $`\varphi (x)`$ has a solution over $``$.

We now distinguish two cases:

Case 1: $`HN_j^{\mathrm{yes}}`$ has measure zero in $`HN_j`$. Thus $`HN_j^{\mathrm{yes}}Z(\widehat{f}_j)`$ for an easy-to-compute polynomial $`\widehat{f}_j`$. In that case, since $`X_i^{\mathrm{yes}}`$ gets mapped into $`HN_j^{\mathrm{yes}}`$, the composition $`f_i=\widehat{f}_j\varphi `$ gives the polynomial associated to $`X_i`$.

Case 2: $`HN_j^{\mathrm{no}}`$ has measure zero in $`HN_j`$. Thus $`HN_j^{\mathrm{no}}Z(\widehat{f}_j)`$ for an easy-to-compute polynomial $`\widehat{f}_j`$. In that case, since $`X_i^{\mathrm{no}}`$ gets mapped into $`HN_j^{\mathrm{no}}`$, $`f_i=\widehat{f}_j\varphi `$ is the polynomial associated to $`X_i`$. ∎

## 5 Ultimate Complexity

Let $`(Y,Y^{\mathrm{yes}})`$ be a problem over $``$, 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`$.

For any machine $`M`$ to solve $`(Y,Y^{\mathrm{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 5, we have

$$Y_i^{\mathrm{yes}}Z(f_i)\text{ or }Y_i^{\mathrm{no}}Z(f_i)$$

Also, for each input size $`s`$, one has a finite number of indices $`i`$ corresponding to components i $`Y_i\overline{Y}`$ of size-$`s`$ input. We can thus maximize over those indices $`i`$:

$$u_M(s)=\underset{i:Y_i^i}{\mathrm{max}}\tau (f_i)$$

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:`$ such that $`M,c>0:xu_M(x)cu(x)`$ and $`M`$ recognizes $`(Y,Y^{\mathrm{yes}})`$. This provides notions such as ‘ultimate logarithmic time’ or ‘ultimate exponential time’.

In , 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^{\mathrm{yes}}`$ was a finite set in $``$). The motivation of this paper was to extend some of the ideas therein and in Chapter 7 of  to non-codimension-1 problems.