33
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 30, 2012 at 16:04
  • 8
    $\begingroup$ @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 .) $\endgroup$ Oct 30, 2012 at 19:03
  • 3
    $\begingroup$ 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! $\endgroup$
    – Jeffε
    Oct 31, 2012 at 4:44
  • 2
    $\begingroup$ @JɛffE: I think the idea is that the encoding should be completely incidental to the problem itself; that it stands on its own as a 'simple' (as opposed to 'easy') problem about natural numbers which one might plausibly ask without even being aware of the SAT problem. $\endgroup$ Oct 31, 2012 at 14:12
  • 2
    $\begingroup$ @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 ..." $\endgroup$ Oct 31, 2012 at 14:48

5 Answers 5

36
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ This is a great example. Something surprising to me: this problem basically asks: “Is $a$ a small quadratic residue mod $b$, i.e. is it a square of some $0 < x \le c$?” If I understand correctly, finding several small quadratic residues mod $N$ is precisely how factoring algorithms work (quadratic sieve, CFRAC, etc), and factoring is not believed to be NP-complete. So it seems that the best algorithms for factoring are based on solving a (presumably easy instance of an) NP-complete problem! $\endgroup$ Nov 29, 2022 at 14:44
  • $\begingroup$ Isn't there a mistake in your equivalent statement? It seems to me that it would reduce to modular SQUARE ROOT. $\endgroup$
    – domotorp
    Apr 24 at 4:53
  • $\begingroup$ No, it's correct. It asks for solutions in nonnegative integers, hence just like the first statement, it's not just a modular square root, but there is also a bound on the root. The only possibly puzzling aspect is that $c$ plays a double role of (the square of) the bound and the residue to be square-rooted (i.e., it stands for both $a$ and $c^2$ from the first statement). $\endgroup$ Apr 24 at 6:36
  • $\begingroup$ Right, I missed that negative integers are not valid! New issue with new reduction: Why would $d$ need to divide $c$? I assume you meant that it needs to divide $x$. $\endgroup$
    – domotorp
    Apr 24 at 11:08
  • $\begingroup$ You are not given $x$, but $a,b,c$. Since $d$ divides $ax^2+by$ no matter what $x,y$ are, the equation $ax^2+by=c$ is unsolvable unless $d\mid c$. $\endgroup$ Apr 24 at 11:49
12
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ +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. $\endgroup$
    – mjqxxxx
    Oct 30, 2012 at 19:30
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I think this problem is quite TM based but of course it is impossible to draw a line. $\endgroup$
    – domotorp
    Oct 31, 2012 at 5:50
  • 1
    $\begingroup$ 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.) $\endgroup$ Oct 31, 2012 at 15:36
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I think this is more natural than Manders-Adleman. Is smaller than $5$ variables and $10$ inequality example possible? $\endgroup$
    – Turbo
    May 24, 2019 at 0:04
  • $\begingroup$ No, 5 variables is the smallest. 10 - not sure. But you can't really have less than 6... $\endgroup$
    – Igor Pak
    May 24, 2019 at 0:21
  • $\begingroup$ 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$?)? $\endgroup$
    – Turbo
    May 24, 2019 at 0:25
  • $\begingroup$ Yes. For fewer variables the problem is in P. $\endgroup$
    – Igor Pak
    May 24, 2019 at 0:28
  • 2
    $\begingroup$ Yes. It's all in our paper and Danny Nguyen's thesis. math.ucla.edu/~pak/papers/Nguyen-thesis.pdf $\endgroup$
    – Igor Pak
    May 24, 2019 at 0:29
1
$\begingroup$

How about the PARTITION problem?

$\endgroup$
3
  • 3
    $\begingroup$ No, as the input is not a number but a set. $\endgroup$
    – domotorp
    Oct 31, 2012 at 5:45
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 31, 2012 at 13:06
  • $\begingroup$ I am sorry if I was vague in the formulation of the question. $\endgroup$
    – domotorp
    Oct 31, 2012 at 13:20

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.