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

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.

Update 2: And after more than four years waiting, Dan Brumleve has given a "better" solution - note that it's still not complete because of the randomized reduction.

• I know of a NEXP-complete tiling problem where the input is an integer n and the problem is to determine if there exists a valid tiling of an n x n grid. If that's interesting to you, I'll look for the paper. – Robin Kothari Oct 30 '12 at 16:04
• @Emil: domotorp's comment was a response to a confusion I had. But it was a misunderstanding on my part so I deleted the comment. I think the input is required to be a single natural number, which should not encode anything. – Robin Kothari Oct 30 '12 at 18:25
• @domotorp: The NP-complete problem I meant is, given $a,b,c\in\mathbb N$, determine whether $ax^2+by-c=0$ has a solution $x,y\in\mathbb N$. Another variant is, given $a,b,c$, determine whether there is $x\le c$ such that $x^2\equiv a\pmod b$. (The result is from dx.doi.org/10.1145/800113.803627 .) – Emil Jeřábek Oct 30 '12 at 19:03
• Why isn't the answer to this question obviously NO? Every NP-hard problem has instances that "encode" a boolean circuit; arguably, that's what being NP-hard means! – Jeffε Oct 31 '12 at 4:44
• @domotorp: perhaps another good "natural" candidate is the problem of finding the minimum addition chains of a single given number $n$: from On the Number of Minimal Addition Chains: "... The problem of finding a minimal addition chain for a set of $m$ numbers is NP-complete. This does not imply as it is sometimes claimed that finding a minimal addition chain for $n$ is NP-complete. However, we can easily deduce that the problem of finding all minimal addition chains for a number $n$ is NP-complete ..." – Marzio De Biasi Oct 31 '12 at 14:48

This problem has a variation with a single integer input:

Does $n$ have a divisor strictly in between its two largest prime factors?

The idea is to use the same randomized reduction from subset sum described in the top answer to the linked question, but with the target range encoded as the largest two primes instead of given separately. The definition has a natural look to it even though it's just a pairing function in disguise.

Here is another variation of the same problem, with a similar reduction from the partition problem:

Is $n$ the product of two integers that differ by less than $n^{\frac{1}{4}}$?

In both reductions we are "camouflaging" a set of integers by finding nearby primes and taking their product. If it is possible to do that in polynomial time then these problems are NP-complete.

I think it's illuminating to look at these examples along with Mahaney's theorem: if $P \ne NP$ and we can find nearby primes, then these sets are not sparse. It's satisfying to get a purely arithmetical statement from complexity theory (even though it's only conjectural and is likely easily provable some other way).

• what do you mean by ' if P≠NP and we can find nearby primes'? – 1.. Feb 1 '17 at 9:46
• @ao., see Peter Shor's answer describing the reduction. For it to be NP-complete we need to be able to find a prime $p$ with $\vert p - n \vert \lt n^a$ in time $O((\log{n})^k)$. I will try to give my own account of all this here later. – Dan Brumleve Feb 1 '17 at 19:24
• Which sets are not dense? – 1.. May 24 '19 at 0:05

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$.

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$.)

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}$.)

• +1, but it's a little hard to argue that the number $n$ is being used in a "natural" way, since it is encoding the input to a particular Turing machine (specifically, the tiling exists iff the Turing machine accepts $x$, where $x$ is the $n$-th in an enumeration of potential input strings). Still a very interesting result. – mjqxxxx Oct 30 '12 at 19:30
• I maximally agree with mjqxxxx. – domotorp Oct 31 '12 at 5:47

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$.

• I think this problem is quite TM based but of course it is impossible to draw a line. – domotorp Oct 31 '12 at 5:50
• To refine domotorp's comment, I would say that the fact that it has to invoke the notion of a Turing machine at all in the problem description rules it out as a 'natural problem about natural numbers'. (If we suppose that a ntaural problem about natural numbers is one whose general format would be consistent e.g. with Fermat having studied it, without supposing too counterfactual a history of mathematics.) – Niel de Beaudrap Oct 31 '12 at 15:36

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.

• I think this is more natural than Manders-Adleman. Is smaller than $5$ variables and $10$ inequality example possible? – 1.. May 24 '19 at 0:04
• No, 5 variables is the smallest. 10 - not sure. But you can't really have less than 6... – Igor Pak May 24 '19 at 0:21
• Is there a reason behind $\geq5$ and $\geq6$? I mean is it proven that all $\leq4$ and finite number of inequalities is in $P$ (likewise all $\leq5$ variables and $\leq5$ inequalities formulation is in $P$?)? – 1.. May 24 '19 at 0:25
• Yes. For fewer variables the problem is in P. – Igor Pak May 24 '19 at 0:28
• Yes. It's all in our paper and Danny Nguyen's thesis. math.ucla.edu/~pak/papers/Nguyen-thesis.pdf – Igor Pak May 24 '19 at 0:29

• No, as the input is not a number but a set. – domotorp Oct 31 '12 at 5:45
• So are you asking for problems for which an instance is exactly one natural number? I don't think that's clear in your question, as you ask for "problems with natural inputs" and your example of the Nim game involves four numbers. – Kevin A. Wortman Oct 31 '12 at 13:06
• I am sorry if I was vague in the formulation of the question. – domotorp Oct 31 '12 at 13:20