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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ Good explicit example. Thankyou. $\endgroup$ Commented 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$ Commented 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$– boumolCommented Aug 11, 2011 at 1:31
$\begingroup$
$\endgroup$
1
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$?
answered Aug 10, 2011 at 23:43
-
$\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$ Commented Aug 11, 2011 at 1:07