Algorithm on integer polynomials

In this homework, we are interested in the complexity of working with univariate polynomials in \(\mathbb{Z}[X]\) (i.e., with integer coefficients).

Prelude: function composition

We use the Deterministic Turing Machine with Output (DTMO) model of computation, whose definition is formally given in the appendix (see Appendix belows for formal definitions). This models allows us to represent the computation of functions (instead of only decision problems that we have seen so far).

Let \(f: \Sigma^* \rightarrow \Sigma^*\) and \(g: \Sigma^* \rightarrow \Sigma^*\) be two functions computed by DTMO \(M_f\) and \(M_g\) in time \(t_f\) and \(t_g\) respectively.

  1. Show that for every \(u \in \Sigma^*\), \(|g(u)| \leq t_g(|u|)\).
  2. Show that there exists a DTMO \(M_{f \circ g}\) computing \(f \circ g\) in time \(t_f \circ t_g\).

Complexity of evaluating polynomials

In this section, we are interested in the complexity of evaluating a given a polynomial \(P \in \mathbb{Z}[X]\) on an integer \(k \in \mathbb{Z}\), that is, of computing the value \(P(k)\).

We encode a number in binary in \(\{0, 1\}^*\) with the following convention. The first bit indicates if the number is positive. If it is 0 then the number is positive if it is \(1\) it is negative. Then the following bits indicate the absolute value of the number, with the rightmost bit being the least significant (i.e., corresponding to \(1\)).

For instance the word \(010\) encodes the number \(2\) and \(110\) encodes the number \(-2\). Observe that the number \(1000010\) also encodes the number \(-2\), hence it is not a bijective representation of numbers. The representation is said to be minimal if the second bit is set to \(1\), or if there is only one bit (in which case the number represented is zero). Hence, there is no leading zero in the binary representation of the number.

Formally, we introduce the function \(\textrm{dec}_2\colon:\{0, 1\}^*\to \mathbb{Z}\) such that for any \(u\in \{0, 1\}^*\), \(\textrm{dec}_2(u) = (-1)^{u_0} \sum_{i=1}^{|u|} u_i 2^{|u|-i-1}\).

  1. Give a DTMO \(M_\textrm{minus}\) that computes the function \(n\in\mathbb{Z}\mapsto -n\) using the binary encoding.

  2. In this question, we let \(\Sigma = \{0,1,\#\}\). We let \(\textrm{PLUS}\) be the function that associates \(a\#b\) to \(c\) where \(a,b,c \in \{0,1\}^*\) such that \(\textrm{dec}_2(a)+\textrm{dec}_2(b) = \textrm{dec}_2(c)\) and \(c\) is the minimal representation of \(\textrm{dec}_2(c)\) (hence no leading zeros in \(c\)). Intuitively, \(\textrm{PLUS}\) takes the binary representation of two numbers and outputs the binary representation of their sum.

    1. Give a DTMO \(M_\textrm{CHECK}\) that given \(u \in \Sigma^*\), writes \(\#\) on the output tape and stops if \(u\) is not in the form \(a\#b\) with \(a,b \in \{0,1\}^*\). Otherwise, it writes \(b\) on the output tape and halts.

    2. Give a DTMO \(M_\textrm{PLUS}\) computing \(\textrm{PLUS}\) in time \(O(n)\).

  3. Horner’s method is a method to evaluate univariate polynomials of degree \(d\) with \(d\) multiplications. It is defined as follows: given a polynomial \(P(X) = \sum_{i=0}^d a_i X^i\) and \(k \in \mathbb{N}\), we let \(b_d := a_d\) and for every \(0 \leq i < d\), \(b_{i} := b_{i+1} \times k + a_{i}\). Show that \(b_0 = P(k)\).

We let \(\textrm{MULT}\) to be the function that associates \(a\#b\) to \(c\) where \(a,b,c \in \{0,1\}^*\) such that \(\textrm{dec}_2(a) \times \textrm{dec}_2(b)=\textrm{dec}_2(c)\).

In the following, we assume we have a Turing machine \(M_\textrm{MULT}\) which is works in polynomial time.

  1. Given a polynomial \(P(X) = \sum_{i=0}^d a_i X^i \in \mathbb{Z}[X]\) and \(k \in \mathbb{Z}\), we denote by \(enc(P,k)\) the word \(\textrm{dec}_2(a_0)\#\dots\#\textrm{dec}_2(a_n)\#\textrm{dec}_2(k)\).

    We let \(\textrm{EVAL} : \Sigma^* \to \Sigma^*\) be the function that maps a word of the form \(enc(P,k)\) to the binary representation of \(P(k)\). It maps every word not in this form to \(\#\).

    Show that \(\textrm{EVAL}\) can be computed in polynomial time on DTMO (dont write explicity the Turing machine but explain how it is going to work).

Complexity of finding integer roots

In this section, we consider the problem of deciding whether a given polynomial \(P(X) = \sum_{i=0}^d a_i X^i\) has a root in \(\mathbb{Z}\), that is, we want to decide the following language: \(\textrm{IntegerRoots}=\{enc(P) \mid P \in \mathbb{Z}[X], \exists k \in \mathbb{Z}, P(k)=0\}\). To simplify, we will assume that \(d\geq 1\) (with \(a_d \neq 0\)).

  1. Show that for every \(k \in \mathbb{Z}\) such that \(P(k) = 0\) then \(|k| \leq \sum_{i=0}^{d-1} |a_i|\).

  2. Deduce that \(\textrm{IntegerRoots}\) is in \(\textrm{NP}\).

  3. Using the nondet module, write a python program for \(\textrm{IntegerRoots}\).

Python Benchmarking

In the following, we represent polynomial in \(\mathbb{Z}[X]\) by its tuple of integers coefficients in Python.

A function \(\textrm{Eval}\) takes a polynomial \(P\) and an integer \(k\) value and returns \(P(k)\). A naïve Python implementation is as follows:

Eval = lambda P,k: sum(P[i]*k**i for i in range(len(P)))
  1. Propose an implementation based on Horner’s method.
  2. Compare the efficiency of both implementation. Describe the methodology used to compare them.

Appendix

Deterministic Turing Machine with Output

A Deterministic Turing Machine with Output (DTMO) is a \(5\)-uplet \((\Sigma, Q, q_0, q_h, \delta)\) where \(\Sigma\) is the input alphabet, \(Q\) is a finite set of states, \(q_0\) is the initial state, \(q_h\) is the halting state and \(\delta : (Q\setminus \{q_h\}) \times \Sigma \times \Sigma \to Q \times \Sigma \times \{-1,0,+1\} \times \Sigma \times \{-1,0,+1\}\) is the transition function.

The memory model is the following: a DTMO has two bi-infinite tapes: the working tape and the output tape, each having a head that can read and write on the tape and move independently, with each tape content being of the form \(\_^\infty u \_^\infty\).

A configuration \(c = (q, u_w, i_w, u_o, i_o)\) is a tuple containing the current state \(q\) of the machine, the words \(u_w\) and \(u_o\) written on the working and output tapes respectively and the positions \(i_w\) and \(i_o\) of the working and output tapes respectively.

Given a configuration \(c = (q, u_w, i_w, u_o, i_o)\), let \(a = u_w[i_w]\), that is, the letter read by the head on the working tape and \(b = u_o[i_o]\) the letter read by the head on the output tape. If \(q \neq q_h\), the configuration following \(c\) is \(\delta(c) = (q', v_w, j_w, v_o, j_o)\) where \(\delta(q, a, b) = (q', a', k_w, b', k_o)\) and:

If \(q = q_h\), the machine stops.

Given a word \(u \in \Sigma^*\), the initial configuration \(c_0(u)\) of \(M\) on input \(u\) is \(c_0(u) = (q_0, \_^\infty u \_^\infty, 1, \_^\infty, 1)\), that is, the working tape starts with the word \(u\) written on it and the output tape is blank.

Given a DTMO \(M\) and a word \(u\), the execution of \(M\) on input \(u\) is the sequence \((c_i)\) defined as: \(c_0 = c_0(u)\) and \(c_{i+1} = \delta(c_i)\) if the state of \(c_i\) is not \(q_h\), otherwise \(c_i\) is the last element of the sequence.

A DTMO \(M\) computes a function \(f : \Sigma^* \to \Sigma^*\) if for every \(u\):


Compiled the: mar. 17 déc. 2024 14:03:14 CET