From: Page 156 of Sipser, M.(2010) Introduction to the Theory of Computation, (2nd Edition) [ or Page 184 of Sipser, M.(2013) Introduction to the Theory of Computation, (3rd Edition)]

Integral root of single variable Polynomials:

Polynomial equations with one variable, x, can be checked if the value of x is an integer.  

Let  D1  =   { p | p is a polynomial over x with an integral root  }   

Example_1:     3x2   + 2x  - 56  = 0  is in the set D1.  This polynomial belongs to D1, because  x = 4

Example_2:   6x2 + 13x  + 6 = 0    does  NOT  belong to   D1   ( x = -1.5   (or x=  -2/3 = -.666)  )

                   (13.5 - 19.5 +6 = 0       with x=  -1.5   )       [Factor example2 as  (3x +2 )(2x +3) = 0   ]

The set D1  is decidable. “Here is a TM,  M1, that recognizes D1: 

M1  = “The input is a polynomial over the variable x.

1.     Evaluate  p with x set successively to the values 0, 1, -1, 2,    -2, 3, -3,  . . . . 

If at any point the polynomial evaluates to 0, accept


The algorithm terminates, because the roots of such a polynomial must be between the values:

           (k *  Cmax /C1 )

Where k is the number of terms in the Polynomial,     Cmax  is the coefficient of the largest absolute value,  and  C1  is the coefficient of the highest order term.       


For example_1,   3x2  + 2x  -  56  = 0,

the roots of the Polynomial must be between:          (3 *  56/3) =  +-56

This polynomial belongs to D1, because  x = 4


For multivariable Polynomials,

Let  D  =   { p | p is a polynomial  with  integral roots  }        is undecidable;  that is, it may run for ever on some input. 

This was the 10th problem on Hilbert’s list?

In 1900, in recognition of their depth, David Hilbert proposed the solvability of all Diophantine problems as the tenth of his celebrated problems. In 1970, a novel result in mathematical logic known as Matiyasevich's theorem settled the problem negatively: in general,  Diophantine problems are unsolvable.

S9: Write a web-based program for demonstrating integral root single variable polynomials. For extra credits, demonstrate integral root two variable polynomials in addition to single variable polynomials. To get started see: