What are some of the natural number theory problems that are npcomplete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.
2 Answers
You can take a look at the papers by Adleman and Manders (not always in this order) from the 70s (at least "Computational complexity of decision procedures for polynomials", "NPcomplete decision problems for quadratic polynomials", "Diophantine complexity"), and the references therein.
One example of the problems they show to be NPcomplete is the following decision problem.
Input: three natural numbers $a,b,c$ (in base $2$),
Output: YES/NO depending whether the equation $ax^2 + by = c$ has solutions (for $x,y$) in the natural numbers.


$\begingroup$ Do you happen to know the proof? I had the opinion Diophantine equations usually have only undecidability results. $\endgroup$ Aug 11, 2011 at 1:09

3$\begingroup$ This example is Theorem 1 in the paper "NPcomplete decision problems for quadratic polynomials". There you can find the proof of the NPhard part, but the fact that it belongs to NP is easily proved because there is a solution for $x,y$ iff there is a solution with $x,y\leq c$ (this bound is enough for showing membership in the class NP). The problem that it is known to be undecidable is the one where you allow multiple variables (not just the two $x,y$) and integer coefficients [in the same paper it is noted that it is known that 9 variable are enough for the undecidability]. $\endgroup$– boumolAug 11, 2011 at 1:31
See pages 249251 of Garey and Johnson, Computers and Intractability, for a dozen NPcomplete problems in Number Theory.
EDIT: A couple of examples, by request.
AN2, Simultaneous incongruences. Given a collection $\lbrace(a_1,b_1),\dots,(a_n,b_n)\rbrace$ of ordered pairs of positive integers with $a_i\le b_i$ for $1\le i\le n$, is there an integer $x$ such that for all $i$, $x\not\equiv a_i\pmod{b_i}$?
AN4, Comparative divisibility. Given sequences $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_m$ of positive integers, is there a positive integer $c$ such that the number of $i$ for which $c$ divides $a_i$ is more than the number
of $j$ for which $c$ divides $b_j$?

$\begingroup$ Hi Gerry: I don't have the book and I can't see it in google book preview. Could you provide some example problems if you have the book? It would greatly help. $\endgroup$ Aug 11, 2011 at 1:07