There are no sparse NP_{W}-hard Sets

Felipe Cucker^{∗} Department of Mathematics City University of Hong Kong 83 Tat Chee Avenue, Kowloon HONG KONG

             e-mail: macucker@math.cityu.edu.hk

Dima Grigoriev IMR Université de Rennes I Campus de Beaulieu, Rennes 35042 FRANCE

             e-mail: dima@maths.univ-rennes1.fr

Abstract. In this paper we prove that, in the context of weak machines over IR, there are no sparse NP-hard sets.

1 Introduction

In [1977] Berman and Hartmanis conjectured that all NP-complete sets are polynomially isomorphic. That is, that for all NP-complete sets A and B, there exists a bijection φ : Σ^{∗} → Σ^{∗} such that x ∈ A if and only if φ(x) ∈ B. In addition both φ and its inverse are computable in polynomial time. Here Σ denotes the set {0, 1} and Σ^{∗} the set of all finite sequences of elements in Σ.

Should this conjecture be proved, we would have as a consequence that no “small” NP-complete set exists in a precise sense of the word “small”. A set S ⊆ Σ^{∗} is said to be sparse when there is a polynomial p such that for all n ∈ IN the subset S_{n} of all elements in S having size n has cardinality at most p(n). If the Berman-Hartmanis conjecture is true, then there are no sparse NP-complete sets.

∗Partially supported by CERG grant 9040393.

In 1982 Mahaney ([Mahaney 1982]) proved this weaker conjecture showing that there exist sparse NP-hard sets if and only if P = NP. After this, a whole stream of reserach developed around the issue of reductions to “small” sets (see [Arvind, Han, Hemachandra, Köbler, Lozano, Mundhenk, Ogiwara, Schöning, Silvestri, and Thierauf 1993]).

In a different line of research, Blum, Shub and Smale introduced in [1989] a theory of computability and complexity over the real numbers with the aim of modelling the kind of computations performed in numerical analysis. The computational model defined in that paper deals with real numbers as basic entities, and performs arithmetic operations on them as well as sign tests. Inputs and outputs are vectors in IR^{n} and decision problems are subsets of IR^{∞}, the disjoint union of IR^{n} for all n ≥ 1. The classes P_{IR} and NP_{IR} —which are analogous to the well known classes P and NP— are then defined and one of the main results in [Blum, Shub, and Smale 1989] is the existence of natural NP_{IR}-complete problems.

Clearly, the sparseness notion defined above for sets over {0, 1} will not define any meaningful class over IR since now the set of inputs of size n is IR^{n} and this is an infinite set. A notion of sparseness over IR capturing the main features of the discrete one (independence of any kind of computability notion and capture of a notion of “smallness”), however, was proposed in [Cucker, Koiran, and Matamala 1997]. Let S ⊆ IR^{∞}. We say that S is sparse if, for all n ≥ 1, the set

S_{n} = {x ∈ S | x ∈ IR^{n}}

has dimension at most log^{k} n for some fixed k. Here dimension is the dimension, in the sense of algebraic geometry, of the Zariski closure of S_{n}.

Using this definition of sparseness the main result of [Cucker, Koiran, and Matamala 1997] proves that there are no sparse NP-complete sets in the context of machines over IR which do not perform multiplications or divisions and branch on equality tests only. Note that this result is not conditioned to the inequality P ≠ NP since this inequality is known to be true in this setting (cf. [Meer 1992]).

A variation on the BSS model attempting to get closer to the Turing machine (in the sense that iterated multiplication is somehow penalized) was introduced by Koiran in [1997]. This model, which Koiran called weak, takes inputs from IR^{∞} but no longer measures the cost of the computation as the number of arithmetic operations performed by the machine. Instead, the cost of each individual operation x∘y depends on the sequences of operations which lead to the terms x and y from the input data and the machine constants.

In this paper we extend Mahaney’s theorem to machines over IR endowed with the weak cost. Again, this is not a conditional result since it is known that P ≠ NP in this context too (cf. [Cucker, Shub, and Smale 1994]). If NP_{W} denotes the class of sets decided in non-deterministic polynomial cost, our main result is the following.

Theorem 1 There are no sparse NP_{W} -hard sets.

2 The weak cost

Let M be a machine over IR, let α_{1}, …, α_{k} be its constants and let x = (x_{1}, …, x_{n}) ∈ IR^{∞}. At any step ν of the computation of M with input x, the intermediate value z ∈ IR produced in this step can be written as a rational function of a and x, z = φ(a, x). This rational function only depends on the computation path followed by M up to ν (i.e. on the sequence steps previously performed by M) and is actually a coordinate of the composition of the arithmetic operations performed along this path (see [Blum, Cucker, Shub, and Smale 1998] for details). Let φ = \frac{g_{ν}}{h_{ν}} be the representation of φ obtained by retaining numerators and denominators in this composition. For example, the representation of the product \frac{g}{h} · \frac{r}{s} is always \frac{gr}{hs} and the one of the addition \frac{g}{h} + \frac{r}{s} always \frac{gs+hr}{hs}. We will now use g_{ν} and h_{ν} to define weak cost.

Definition 1 The weak cost of any step ν is defined to be the maximum of deg(g_{ν}), deg(h_{ν}), and the maximum bit size of the coefficients of g_{ν} and h_{ν}. For any x ∈ IR^{∞} the weak cost of M on x is defined to be the sum of the costs of the steps performed by M with input x.

The class P_{W} of sets decided within weak polynomial cost is now defined by requiring that for each input of size n the weak cost of its computation is bounded by a polynomial in n. A set S is decided in weak nondeterministic polynomial cost (we write S ∈ NP_{W}) if there is a machine M working within weak polynomial cost satisfying the following: for each x ∈ IR^{∞}, x ∈ S if and only if there is y ∈ IR^{∞} with size polynomial in n such that M accepts the pair (x, y).

Remark 1 The definitions above do not fully coincide with those given in [Koiran 1997] since this reference requires the representation of the rational functions φ above to be relatively prime. The definitions we give here, which are taken from [Blum, Cucker, Shub, and Smale 1998], are essentially equivalent.

3 The main result

Let n ≥ 1. Consider the polynomial

f_{n} = x_{1}^{2^{n}} + … + x_{n}^{2^{n}} − 1

and let C_{n} = {x ∈ IR^{n} | f_{n}(x) = 0}. The polynomial f_{n} is irreducible and the dimension of C_{n} is n − 1. Let C ⊂ IR^{∞} be given by C = ∪C_{n}. We know (cf. [Cucker, Shub, and Smale 1994]) that C ∈ NP_{W} but C ∉ P_{W}.

Let S ⊂ IR^{∞} be a NP_{W} -hard set. Then C reduces to S. That is, there exists a function φ : IR^{∞} → IR^{∞} computable with polynomial cost such that, for all x ∈ IR^{∞}, x ∈ C ⟺ φ(x) ∈ S. For each n ≥ 1, the restriction of φ to IR^{n} is a piecewise rational function. Our first result, Proposition 2, gives some properties of this function. It uses the following simple fact in real algebraic geometry whose proof can be found in Chapter 19 of [Blum, Cucker, Shub, and Smale 1998].

Proposition 1 Let f ∈ IR[x_{1}, …, x_{n}] be an irreducible polynomial such that the dimension of its zero set Z(f) ⊆ IR^{n} is n − 1. Then, for any polynomial g ∈ IR[x_{1}, …, x_{n}], g vanishes on Z(f) if and only if g is a multiple of f.

Proposition 2 Let n be sufficiently large. There exist x ∈ C_{n} and U ⊂ IR^{n} an open ball centered at x such that the restriction of φ to U is a rational map h : U → IR^{m} for some m bounded by a polynomially in n. In addition, if h_{1}, …, h_{m} are the coordinates of h, then the degrees of the numerator and denominator of h_{i} are also bounded by a polynomial in n for i = 1, …, m.

Proof. Let M be a machine computing φ within weak polynomial cost. By unwinding the computation of M in a standard manner we obtain an algebraic computation tree of depth polynomial in n. To each branch η in this tree one associates a set D_{η} ⊆ IR^{n} such that the D_{η} partition IR^{n} (i.e. ∪D_{η} = IR^{n} and D_{η} ∩D_{γ} = ∅ for η ≠ γ). In addition, each branch η computes a rational map h_{η} and φ_{|D_{η}} = h_{η}. The set D_{η} is the set of points in IR^{n} satisfying a system

⋀_{i=1}^{s_{η}} q_{i}(x_{1}, …, x_{n}) ≥ 0 ∧ ⋀_{i=s_{η}+1}^{t_{η}} q_{i}(x_{1}, …, x_{n}) < 0  (1)

where the q_{i}(X_{1}, …, X_{n}) are the rational functions tested along the branch. Since M works within weak cost, the numerators and denominators of the q_{i} as well as those of h_{η} have degrees bounded by a polynomial in n.

Everything we need now to see is that for some branch η, D_{η} contains an open neighbourhood of a point x ∈ C_{n}.

To do so first notice that, by replacing each q_{i} by the product of its numerator and denominator, we can assume that the q_{i} are polynomials. Also, by writing q_{i} ≥ 0 as q_{i} = 0 ∨ q_{i} > 0 and distributing the disjunctions in (1) we can express D_{η} as a finite union of sets satisfying a system

⋀_{i=1}^{s} q_{i}(x_{1}, …, x_{n}) = 0 ∧ ⋀_{i=s+1}^{t} q_{i}(x_{1}, …, x_{n}) < 0.  (2)

We have thus described IR^{n} as a union of sets which are solutions of systems like (2). Since this union is finite there exists one such set D containing a subset H of C_{n} of dimension n−1. Let D be the solution of a system like (2). We claim that there are no equalities in such system. Assume the contrary. Then there is a polynomial q such that H ⊂ Z(q). Since dim H = n − 1 and C_{n} is irreducible this implies that q(C_{n}) = 0 and, by Proposition 1, that q is a multiple of f_{n}. Since deg f_{n} = 2^{n} this is not possible for sufficiently large n.

The above implies that D is an open set from which the statement follows.

For the next result we keep the notation of the statement of Proposition 2.

Proposition 3 Let k = dim h(U). Then, there exist indices i_{1}, …, i_{k} ∈ {1, …, m}, a polynomial g ∈ IR[y_{1}, …, y_{k}] and a rational function q ∈ IR(x_{1}, …, x_{n}) with both numerator and denominator relatively prime with f_{n} such that

g(h_{i_{1}}, …, h_{i_{k}}) = f_{n}^{ℓ}q

for some ℓ > 0.

Proof. First, notice that, since dim(h(U)) = k, there exist i_{1}, …, i_{k} ∈ {1, …, m} such that the functions h_{i_{1}}, …, h_{i_{k}} are algebraically independent. We want to show that dim(U ∩ C_{n}) < k. To do so let X = h(U), Y = h(U −C_{n}) and Z = h(U ∩C_{n}). We have that all X, Y and Z are semialgebraic subsets of IR^{m}. In addition, Z is contained in the closure of Y with respect to the Euclidean topology relative to X since h is continuous and Y ∩ Z = ∅ since h is the restriction of φ to U and φ is a reduction.

From here it follows that Z is included in the boundary of Y relative to X. Hence, dim Z < dim Y = dim X (see e.g. Proposition 2.8.12 of [Bochnak, Coste, and Roy 1987]).

The above shows that dim h(U ∩ C_{n}) < k. Therefore, there exists g ∈ IR[y_{1}, …, y_{k}] such that, for all x ∈ U ∩ C_{n}, g(h_{i_{1}}(x), …, h_{i_{k}}(x)) = 0. Write this as a rational function g(h) = a/b with a, b ∈ IR[x_{1}, …, x_{n}] relatively prime. Then a(C_{n}) = 0 and a ≠ 0 (since h_{i_{1}}, …, h_{i_{k}} are algebraically independent). By Proposition 1 this implies that there exists r ∈ IR[x_{1}, …, x_{n}] such that a = rf_{n}. If ℓ is the largest power of f_{n} dividing a then the result follows by taking q = \frac{ar′}{b} where r′ is the quotient of r divided by f_{n}^{ℓ−1}.

Proposition 4 Let n be sufficiently large. Then, k ≥ n.

Proof. To simplify notation, assume that i_{j} = j for j = 1, …, k. Also, let d be a bound for the degrees of the numerators and denominators of the h_{j}. Recall from Proposition 2 that d is bounded by a polynomial in n.

By Proposition 3 we have that there exists q ∈ IR(x_{1}, …, x_{n}) relatively prime with f_{n} such that

f_{n}^{ℓ}q = g(h_{1}, …, h_{k})

for a certain ℓ ≥ 1. Taking derivatives on both sides we obtain that, for all x ∈ IR^{n},

∇(f_{n}^{ℓ}q)(x) = ∇(g)(h(x)) ∘ Dh(x)  (3)

where ∇ denotes the gradient and Dh(x) is the Jacobian matrix of h at x.

Assume that k < n. Transposing (3) one sees that ∇(f^{ℓ}q)(x) is the image of a vector of dimension k. Thus, there exists a linear dependency among the first k + 1 coordinates of ∇(f^{ℓ}q)(x)

∑_{i=1}^{k+1} λ_{i} \frac{∂f_{n}^{ℓ}q}{∂x_{i}} = 0  (4)

and the coefficients λ_{i} of this linear dependency are the determinants of some minors of Dh(x). Thus, for i = 1, …, k + 1, λ_{i} is a rational function of x whose numerator and denominator have degrees bounded by kd. Since the submatrix of Dh(x) obtained by keeping its first k + 1 rows contains at most k(k + 1) different denominators, multiplying equation (4) by the product of all of all of them allows one to assume that the λ_{i} are polynomials with degree at most kd(k + 1).

By the product rule we get

∑_{i=1}^{k+1} λ_{i} (ℓf_{n}^{ℓ−1}q \frac{∂f_{n}}{∂x_{i}} + f_{n}^{ℓ} \frac{∂q}{∂x_{i}} ) = 0

i.e.

ℓf_{n}^{ℓ−1}q ∑_{i=1}^{k+1} λ_{i} \frac{∂f_{n}}{∂x_{i}} + f_{n}^{ℓ} ∑_{i=1}^{k+1} λ_{i} \frac{∂q}{∂x_{i}} = 0.

Since f_{n}^{ℓ} divides the second term above it must also divide the first from which, using that f_{n} and q are relatively prime, it follows that f_{n} divides ∑_{i=1}^{k+1} λ_{i} \frac{∂f_{n}}{∂x_{i}}. That is, there exists a polynomial p such that

f_{n}p = ∑_{i=1}^{k+1} λ_{i} \frac{∂f_{n}}{∂x_{i}}

i.e.

p (∑_{i=1}^{n} x_{i}^{2^{n}} − 1) = 2^{n} ∑_{i=1}^{k+1} λ_{i}x_{i}^{2^{n}−1}.

Now, for n large enough, the degrees of the λ_{i} are smaller than 2^{n} − 1 since kd(k + 1) is polynomial in n. This implies that the degree of p must also be bounded by kd(k + 1). But then, for each i ≤ k + 1, px_{i}^{2^{n}} = λ_{i}x_{i}^{2^{n}−1}, i.e., px_{i} = λ_{i}. And from here it follows that −p = 0, a contradiction.

Theorem 1 follows immediately from Proposition 4.

Remark 2 The result of Theorem 1, together with that in [Cucker, Koiran, and Matamala 1997], supports the conjecture that there are no sparse NPhard sets over the reals unless P = NP. There are two main settings with this remains to be proved. On the one hand, machines which do not multiply nor divide but which branch over sign tests. On the other hand, the unrestricted case in which the machine can multiply or divide (and branch over sign tests) with unit cost. In these two cases, the result seems harder since there is no proof that P ≠ NP. In the first case, we would like to remark that Mahaney’s conjecture is false if many-one reductions are replaced by Turing reductions. For the latter, Fournier and Koiran proved in [Fournier and Koiran 2000] that any NP-complete set in the Boolean setting (i.e. over {0, 1}) is NPcomplete over the reals with addition and order for Turing reductions. Since the subsets of elements of size n of any such set S have dimension 0 the sparseness of S is immediate. For more on this see [Fournier 2000].

References

Arvind, V., Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf (1993). Reductions to sets of low information content. In K. Ambos-Spies, S. Homer, and U. Schöning (Eds.), Complexity Theory: current research, pp. 1–45. Cambridge University Press.

Berman, L. and J. Hartmanis (1977). On isomorphism and density of NP and

other complete sets. SIAM Journal on Computing 6, 305–322. Blum, L., F. Cucker, M. Shub, and S. Smale (1998). Complexity and Real

Computation. Springer-Verlag. Blum, L., M. Shub, and S. Smale (1989). On a theory of computation and

complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc. 21, 1–46.

Bochnak, J., M. Coste, and M.-F. Roy (1987). Géométrie algébrique réelle.

Springer-Verlag. Cucker, F., P. Koiran, and M. Matamala (1997). Complexity and dimension.

Information Processing Letters 62, 209–212. Cucker, F., M. Shub, and S. Smale (1994). Complexity separations in Koiran’s

weak model. Theoretical Computer Science 133, 3–14. Fournier, H. (2000). Sparse NP-complete problems over the reals with addition.

Technical Report 2000-12, LIP. Fournier, H. and P. Koiran (2000). Lower bounds are not easier over the

reals: Inside PH. In 28th International Colloquium on Automata, Languages and Programming, Volume 1853 of Lect. Notes in Comp. Sci., pp. 832–843. Springer-Verlag.

Koiran, P. (1997). A weak version of the Blum, Shub & Smale model. J. Comput. System Sci. 54, 177–189. A preliminary version appeared in 34th annual IEEE Symp. on Foundations of Computer Science, pp. 486–495, 1993.

Mahaney, S. (1982). Sparse complete sets for NP: Solution of a conjecture by

Berman and Hartmanis. J. Comput. System Sci. 25, 130–143. Meer, K. (1992). A note on a P ≠ NP result for a restricted class of real machines.

Journal of Complexity 8, 451–453.