Ultimate Polynomial Time

Gregorio Malajovich^{∗}

January 21, 1999

Abstract

The class UP of ‘ultimate polynomial time’ problems over ℂ is introduced; it contains the class P of polynomial time problems over ℂ.

The τ-Conjecture for polynomials implies that UP does not contain the class of non-deterministic polynomial time problems definable without constants over ℂ. This latest statement implies that P ≠ N P over ℂ.

A notion of ‘ultimate complexity’ of a problem is suggested. It provides lower bounds for the complexity of structured problems.

1 Introduction

A model of Computation and Complexity over a ring was developed in [2] and [1], generalizing the classical N P-completeness theory [3]. 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 [1] for background). This model shares some of the features of the classical (Turing) model of computation (There is a discussion in [7]). It is known [5, 9] that the hypothesis BPP ⊉ N P in the Turing setting implies P ≠ N P over ℂ. (BPP stands for Bounded Probability Polynomial Time. If BPP would happen to contain N P, then there would be polynomial time randomized algorithms for such tasks as factorizing large integers or breaking most modern cryptographic systems).

∗Departamento de Matemática 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

In [8, 1, 10], the hypothesis P ≠ N P 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} , ⋯, s_{τ}

where s_{i} is, for i ≥ 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 compute the polynomial s_{τ}(x).

Given a polynomial f ∈ ℤ[x], the quantity τ(f) is defined as the smallest τ such that there exists a straight-line program s_{0}, ⋯, s_{τ} computing f(x). For instance, τ(x^{2^{n}} − 1) = 2 + n. Similarly, if g ∈ ℤ[x_{1}, ⋯, x_{n}], then τ(g) is the minimal length of a straight-line program s_{0} = 1, s_{1} = x_{1}, ⋯, s_{n} = x_{n}, s_{n+1}, ⋯, s_{τ} = g(x).

The τ Conjecture for Polynomials . There is a constant a > 0 such that for any univariate polynomial f ∈ ℤ[x],

n(f) < τ(f)^{a}

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

It is known [1] that the τ-Conjecture for polynomials implies P ≠ N P over ℂ. A main step towards this result is the fact that, if the τ-Conjecture is true, then the polynomials

p_{d}(x) = (x − 1)(x − 2) ⋯ (x − d)

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

τ ( p_{d}(x)f(x) ) < a (log_{2} d)^{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 UP, of ultimate polynomial time problems. This class will contain P ∩ K, where P is the class of problems decidable in polynomial time and K is the class of problems definable without constants (See [4] and Definition 1 below). Moreover:

Theorem 1. The implications (a) ⇒ (b) ⇒ (c) ⇒ (d) are true:

(a) The τ-conjecture for polynomials.

(b) ∀d, p_{d} is ultimately hard to compute.

(c) UP ⊉ N P ∩ K over ℂ.

(d) P ≠ N P over ℂ.

The implication (a) ⇒ (b) ⇒ (d) appears in [1], the hypothesis (c) inbetween is new. It is at least as likely as the τ-conjecture, while still implying P ≠ N P .

We will also show a N P-hardness result for the class UP: there is a structured problem (HN, HN^{yes}) ∈ N P ∩ K, such that:

Theorem 2. UP ⊉ N P ∩ K over ℂ if and only if (HN, HN^{yes}) ∉ UP over ℂ.

The problem (HN, HN^{yes}) is precisely the (structured) Hilbert Nullstellensatz, known to be N P-complete over ℂ ([1]).

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 [1] that ℂ^{∞} is the disjoint union

ℂ^{∞} = ⨆_{i=0,1,···} ℂ^{i}

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

Size : ℂ^{∞} → ℕ
x ↦ Size(x) = i such that x ∈ ℂ^{i}

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

M(x) = 0 ⇔ x ∈ X

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 [1]). 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 [4]. 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 = {π}.

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}, x ∈ L 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 [4]. 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 L ⊆ K^{∞} be a problem which is definable without constants. If L ∈ P, 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 K.

We will need crucially in the sequel the notion of a structured problem. A structured problem is a pair (X, X^{yes}), X^{yes} ⊆ X ⊆ ℂ^{∞}. A non-structured problem X can always be written as the structured problem (ℂ^{∞}, X). The class UP will be meaningful only as a class of structured problems. But first of all, recall that Definition 2. A structured problem (X, X^{yes}) belongs to the class P if and only if X ∈ P and X^{yes} ∈ P.

Definition 3. A structured problem (X, X^{yes}) belongs to the class K if and only if X ∈ K and X^{yes} ∈ K.

Definition 4. A structured problem (X, X^{yes}) belongs to the class N P if and only if:

(1) The problem X belongs to the class P.

(2) There is a machine M with input x, g such that

x ∈ X and ∃g ∈ ℂ^{∞} s.t. M(x, g) = 0 ⇔ x ∈ X^{yes}

(3) Furthermore, there is a polynomial p such that, for all x ∈ X^{yes}, there is g ∈ ℂ^{∞} such that M(x, g) = 0 and the running time of M with input x, g is no more than p(Size(x)).

Example 1. Let HN be the class of all lists (m, n, f_{1}, ⋯, f_{m}) where f_{1}, ⋯, f_{m} are polynomials in n variables. Each polynomial f = ∑ f_{I}x^{I} is represented sparsely by a list of monomials (S, m_{1}, ⋯, m_{S}), where each monomial is a list (f_{I}, I_{1}, ⋯, 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 P.

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

The definition above of the structured problem (HN, HN^{yes}) can be translated into first order constant-free formulae over ℂ. Therefore, (HN, HN^{yes}) ∈ K. It is also N P-complete over the complex numbers (Theorem 1 in Chapter 5 of [1]).

Example 2. Let

X = {(m, x) ∈ ℕ × ℂ}
X^{yes} = {(m, x) ∈ X such that x ∈ {1, 2, ⋯, m}}

with the convention that m is in bit representation, while x is a complex number. Hence, Size((m, x)) = O(1 + ⌈log_{2}(m)⌉). Then the problem (X, X^{yes}) is in N P over ℂ. The machine M(x, g) can be constructing by guessing the bit decomposition g_{i} of x, and computing x − ∑ g_{i}2^{i}.

Again, (X, X^{yes}) is definable without constants.

3 Construction of the class UP

In Chapter 7 of [1], it is proved that if the problem (X, X^{yes}) from Example 2 would happen to belong to the class P, then condition (b) in Theorem 1 would be false. Therefore (b) implies P ≠ N P over ℂ.

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

Let (X, X^{yes}) be a structured problem with X ∈ P. We denote by X ∩ℂ^{i} the set {x ∈ X : 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} = ⨆_{i=0,1,···} \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 = Size(x), x ∈ X_{j}. We can further define:

X_{j}^{yes} = X_{j} ∩ X^{yes}
X_{j}^{no} = X_{j} \ X^{yes}

(See Figure 1). Using this notation,

This is Problem (X, X^{yes}) from Example 2, 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}.

Figure 1: (X, X^{yes}) from Example 2

Definition 5. The class UP is the class of all structured problems (X, X^{yes}) such that X ∈ P and for all X_{i}, there is a non-zero polynomial f_{i} ∈ ℤ[x_{1}, ⋯, x_{s_{i}}], where s_{i} = Size(x) for x ∈ X_{i}, with the following properties:

(1) τ(f_{i}) is polynomially bounded in S_{i}.

(2) X_{i}^{yes} ⊆ Z(f) or X_{i}^{no} ⊆ Z(f)

Proposition 1. P ∩ K ⊆ UP

Proof of Proposition 1. Let (X, X^{yes}) be in P ∩ K. Let M = M(x) be the machine that recognizes x ∈ X^{yes} in polynomial time, where the input x is assumed to be in \overline{X}. Although it is possible that an x ∈ X_{i} is not in X, it is still possible to recognize x ∈ X^{yes} in polynomial time. Indeed, X is also in P. The machine M(x) will check x ∈ X and x ∈ X^{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 x ∈ X_{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 x ∈ X_{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}^{yes} or all in its complementary X_{i}^{no}.

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}).

4 Proof of the Theorems

Proof of Theorem 1.

(a) ⇒ (b) is trivial, refer to [1] Chapter 7.

(b) ⇒ (c): Let (X, X^{yes}) be the problem in Example 2. 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, ⋯, 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 UP. It does belong to N P ∩ K, so UP ⊉ N P ∩ K .

(c) ⇒ (d) : Using Theorem 2, Condition (c) implies that (HN, HN^{yes}) ∉ UP. However, since (HN, HN^{yes}) ∈ K, Proposition 1 implies (HN, HN^{yes}) ∉ P. Hence P ≠ N P over ℂ.

Proof of Theorem 2. Let (X, X^{yes}) ∈ N P∩K and assume that (HN, HN^{yes}) ∈ UP. We have to show that (X, X^{yes}) ∈ UP.

For each X_{i}, one can embed (X_{i}, X_{i}^{yes}) into some (HN_{i}, HN_{i}^{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^{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 ϕ(x) be the combined Register Equations of machines M and N for time T (Theorem 2 in Chapter 3 of [1]). Thus, ϕ(x) is a system of polynomial equations with integer coefficients and indeterminate coefficients x_{1}, x_{2}, · · ·. The polynomial system ϕ(x) can be constructed in polynomial time from x, and the size of ϕ(x) is polynomially bounded by the size of x.

We claim that ϕ(X_{i}) is contained in some HN_{j}, and that in that case ϕ(X_{i}^{yes}) ⊆ HN_{j}^{yes} and ϕ(X_{i}^{no}) ⊆ HN_{j}^{no}.

Indeed, X_{i} ⊆ ℂ^{s} for some s, and ϕ(ℂ^{s}) ⊆ HN_{j} for some j. Then x ∈ X_{i} belongs to X^{yes} if and only if the corresponding ϕ(x) has a solution over ℂ.

We now distinguish two cases:

Case 1: HN_{j}^{yes} has measure zero in HN_{j}. Thus HN_{j}^{yes} ⊆ Z(f̂_{j}) for an easy-to-compute polynomial f̂_{j}. In that case, since X_{i}^{yes} gets mapped into HN_{j}^{yes}, the composition f_{i} = f̂_{j} ∘ ϕ gives the polynomial associated to X_{i}.

Case 2: HN_{j}^{no} has measure zero in HN_{j}. Thus HN_{j}^{no} ⊆ Z(f̂_{j}) for an easy-to-compute polynomial f̂_{j}. In that case, since X_{i}^{no} gets mapped into HN_{j}^{no}, f_{i} = f̂_{j} ∘ ϕ is the polynomial associated to X_{i}.

5 Ultimate Complexity

Let (Y, Y^{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^{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}^{yes} ⊆ Z(f_{i}) or Y_{i}^{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) = max_{i:Y_{i}⊆ℂ^{i}} τ(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^{yes}). This provides notions such as ‘ultimate logarithmic time’ or ‘ultimate exponential time’.

In [6], 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 ℂ). The motivation of this paper was to extend some of the ideas therein and in Chapter 7 of [1] to non-codimension-1 problems.

References

[1] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Complexity and Real Computation. Springer, 1998.

[2] Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: N P-completeness, recursive functions and universal machines. Bulletin of the AMS, 21(1), 1989.

[3] Michael R. Garey and David S. Johnson. Computers and intractability. W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences.

[4] Pascal Koiran. Elimination of constants from machines over algebraically closed fields. J. Complexity, 13(1):65–82, 1997.

[5] Pascal Koiran. A weak version of the Blum, Shub, and Smale model. Journal of Computer and System Sciences, 54(1, part 2):177–189, 1997. 1st Annual Dagstuhl Seminar on Neural Computing (1994).

[6] Gregorio Malajovich. Lower bounds for some decision problems over ℂ. Preprint, MSRI, 1999.

[7] Gregorio Malajovich and Klaus Meer. On the structure of N P_{ℂ}. SIAM Journal on Computing, 28(1), 1999.

[8] Mike Shub and Steve Smale. On the intractability of Hilbert’s Nullstellensatz and an algebraic version of P = N P. Duke Mathematical J., 81:47–54, 1995.

[9] Steve Smale. Manifestations of computational complexity. Lecture given at the Introductory Workshop on Foundations of Computational Mathematics and Symbolic Computation in Geometry and Analysis, MSRI, August 1998. Lecture on video at www.msri.org.

[10] Steve Smale. Mathematical problems for the next century. Math. Intelligencer, 20(2):7–15, 1998.