Is there a natural problem on the naturals that is NP-complete?

Question

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there any natural problems, i.e. ones that do not use some encoding and special interpretation of the digits? For example "Is n a prime?" is such a natural problem, but this one is in P. Or "Who wins the Nim game with heaps of size 3, 5, n, n?" is another problem that I consider natural, but we also know this to be in P. I am also interested in other complexity classes instead of NP.

Update: As pointed out by Emil Jeřábek, given $a,b,c\in \mathbb N,$ to determine whether $ax^2+by-c=0$ has a solution over the naturals is NP-complete. This is exactly what I had in mind as natural, except that here the input is three numbers instead of just one.

Answer 1

Based on the discussion, I’ll repost this as an answer.

As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$.

NB: $0$ is a natural number.

The problem can be equivalently stated as follows: given $b,c\in\mathbb N$, determine whether the quadratic $x^2+by-c=0$ has a solution $x,y\in\mathbb N$.

[The original paper states the problem with $ax^2+by-c$, but it is not hard to see that one can reduce it to the case $a=1$.

For the record, the reduction of the first problem to the second one is as follows: given $a,b,c\in\mathbb N$, $b>0$, let $c'\le c^2$ be maximal such that $c'\equiv a\pmod b$, i.e., $c'=a+b\lfloor(c^2-a)/b\rfloor$. If $c'<0$, the congruence $x^2\equiv a\pmod b$ has no solution with $0\le x\le c$. Otherwise, it has such a solution iff there are solutions $x,y\ge0$ to $x^2+by-c'=0$.]

[While we are at it, here is a reduction of solvability in $\mathbb N$ of the more general equations $ax^2+by-c=0$ (where $a,b,c\in\mathbb N$) to the first problem. Let $d=\gcd(a,b)$. If $d\nmid c$, the problem has no solution even in $\mathbb Z$. Otherwise, we can divide out $d$, hence we may assume $\gcd(a,b)=1$. Then $ax^2+by-c=0$ has a solution with $x,y\ge0$ iff $x^2\equiv a^{-1}c\pmod b$ has a solution with $0\le x\le\lfloor\sqrt{c/a}\rfloor$.]

Answer 2

Here's a $\text{NEXP}$-complete problem with a single natural number as the input.

The problem is about tiling an $n \times n$ grid with a fixed set of tiles and constraints on adjacent tiles and tiles on the boundary. All of this is part of the specification of the problem; it is not part of the input. The input is only the number $n$. The problem is $\text{NEXP}$-complete for some choice of tiling rules as shown in

D. Gottesman, S. Irani, "The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems," Proc. 50th Annual Symp. on Foundations of Computer Science, 95-104 (2009), DOI: 10.1109/FOCS.2009.22. Also arXiv:0905.2419.

The problem is defined on page 5 of the arxiv version.

Additionally, they also define a similar problem that is $\text{QMA}_\text{EXP}$-complete, which is the bounded-error quantum analog of $\text{NEXP}$. (The classical bounded error analog of $\text{NEXP}$ is $\text{MA}_\text{EXP}$.)

Answer 3

I think that using one of the time-bounded variants of Kolmogorov complexity you can build a problem that uses only the binary representation of a number and (I think) is unlikely to be in $\mathsf{P}$; informally it is a decidable version of the problem "Is $n$ compressible?":

Problem: Given $n$, does a Turing machine $M$ exist such that $|M| < l$ and $M$ on a blank tape outputs $n$ in less than $l^2$ steps, where $l = \lceil \log{n} \rceil$ is the length of the binary representation of $n$

It is clearly in $\mathsf{NP}$, because given $n$ and $M$, just simulate $M$ for $l^2$ steps and if it halts compare the result with $n$.

Answer 4

Our FOCS'17 paper on the Short Presburger Arithmetic is an example of a "natural" problem which is NP-c, and uses a constant number $C$ of integers in the input, say $C< 220$. It is different from Manders-Adleman in that the constraints are all inequalities. See Gil Kalai's blog post for some background.

Answer 5

How about the PARTITION problem?