31

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.

domotorp
  • 13,931
  • 37
  • 93
  • 1
    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
  • What about problems like subset sum? The input is a set of integers, similar to your nim example. – Evgenij Thorstensen Oct 30 '12 at 17:40
  • 1
    I’m rather confused by your comment replying to yourself, but should I take it to mean you only allow a single number as the input? I’d think Manders–Adleman is a quite natural problem. – Emil Jeřábek Oct 30 '12 at 17:40
  • the word "natural" is used all over CS and resists strict defn.... there is a problem listed in Garey & Johnson relating to modulo arithmetic.... – vzn Oct 30 '12 at 17:42
  • 2
    @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
  • @Emil: What is Manders-Adleman? I have found many papers by them and some problems that take two integers as inputs. Ps. I have deleted my old comment. – domotorp Oct 30 '12 at 18:55
  • @Robin: Yes, I would be very much interested in the NEXP-complete tiling thing. – domotorp Oct 30 '12 at 18:56
  • @Evgenij: I want the input to be only one integer, similar to my nim example. – domotorp Oct 30 '12 at 18:57
  • @vzn: Yes, I know natural has no mathematical definition. I use it to mean that n should not encode anything. If the G&J problem fits, then I would be interested in it. – domotorp Oct 30 '12 at 18:58
  • 8
    @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 http://dx.doi.org/10.1145/800113.803627 .) – Emil Jeřábek Oct 30 '12 at 19:03
  • @emil in my memory that is also the one in Garey-Johnson. worthy of an answer imho – vzn Oct 30 '12 at 20:36
  • 3
    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 04:44
  • have the same issue but think there is a real question here if someone asks for the "simplest" NP-complete number theory problem. which poster didnt in the question, but did apply that tag. on the other hand, answers that make a good case for some POV on what "natural" constitutes seem close too. the word "natural" shows up in many CS papers but is defined often informally & based on context... – vzn Oct 31 '12 at 05:02
  • 2
    @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. – Niel de Beaudrap Oct 31 '12 at 14:12
  • 2
    @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
  • 1
    similar question/answers on mathoverflow here Number theory and NP-complete – vzn Nov 02 '12 at 18:56
  • thx, vzn for the link! – domotorp Nov 02 '12 at 20:35

5 Answers5

35

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

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
  • 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! – ShreevatsaR Nov 29 '22 at 14:44
10

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

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
  • 3
    +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 05:47
2

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

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • I think this problem is quite TM based but of course it is impossible to draw a line. – domotorp Oct 31 '12 at 05:50
  • 1
    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
2

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.

Igor Pak
  • 812
  • 5
  • 15
  • I think this is more natural than Manders-Adleman. Is smaller than $5$ variables and $10$ inequality example possible? – Turbo May 24 '19 at 00: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 00: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$?)? – Turbo May 24 '19 at 00:25
  • Yes. For fewer variables the problem is in P. – Igor Pak May 24 '19 at 00:28
  • Is a reference available for this claim? – Turbo May 24 '19 at 00:28
  • 2
    Yes. It's all in our paper and Danny Nguyen's thesis. http://www.math.ucla.edu/~pak/papers/Nguyen-thesis.pdf – Igor Pak May 24 '19 at 00:29
1

How about the PARTITION problem?

Kevin A. Wortman
  • 383
  • 1
  • 6
  • 3
    No, as the input is not a number but a set. – domotorp Oct 31 '12 at 05:45
  • 1
    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