On the Bounded Version of Hilbert's Tenth Problem
by
Chris Pollett
San Jose State University

Hilbert's Tenth problem concerned the decidability of Diophantine equations over the integers. Its negative solution, Matiyassevich's theorem, amounted to showing that the class of formulas of the form

( exists --> y   )P( --> x   , --> y   )=Q( --> x   , --> y   )

where P, Q are polynomials with natural number coefficients is equivalent to the class of recursively enumerable sets. The bounded form of Hilbert's Tenth problem is whether the NP-predicates are the class D of predicates given by formulas of the form

( exists --> y   )[( å j  yj <= 2|\sumixi|k) /\ P( --> x   , --> y   )=Q( --> x   , --> y   )]

where P, Q are polynomials with natural coefficients. This problem is related to the average case completeness of certain NP-problems.

In this talk we give lower bounds on the provability of both these problems in weak fragments of arithmetic. We show the theory I⁵E cannot prove D=NP. Here I^mE has a finite set of axioms and induction on bounded existential formulas up to m lengths of a number for the language L₂, which has the sybmbols <= , 0, S, +, x·y, |x|, 2^|x||y|, \lfloorx/2ⁱ \rfloor, and limited subtraction. We use the non-provability of D=NP to show that I⁵E cannot prove the Matiyassevich's theorem.

Date received: March 5, 2002