7
$\begingroup$

What are some of the natural number theory problems that are np-complete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.

$\endgroup$

2 Answers 2

16
$\begingroup$

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", "NP-complete decision problems for quadratic polynomials", "Diophantine complexity"), and the references therein.

One example of the problems they show to be NP-complete 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.

$\endgroup$
3
  • $\begingroup$ Good explicit example. Thankyou. $\endgroup$
    – user16007
    Aug 11, 2011 at 1:08
  • $\begingroup$ Do you happen to know the proof? I had the opinion Diophantine equations usually have only undecidability results. $\endgroup$
    – user16007
    Aug 11, 2011 at 1:09
  • 3
    $\begingroup$ This example is Theorem 1 in the paper "NP-complete decision problems for quadratic polynomials". There you can find the proof of the NP-hard 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$
    – boumol
    Aug 11, 2011 at 1:31
7
$\begingroup$

See pages 249-251 of Garey and Johnson, Computers and Intractability, for a dozen NP-complete 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$?

$\endgroup$
1
  • $\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$
    – user16007
    Aug 11, 2011 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.