<p>Based on the discussion, I’ll repost this as an answer.</p>
<p>As proved by <a href="http://dx.doi.org/10.1145/800113.803627" rel="nofollow noreferrer">Manders and Adleman</a>, the following problem is NP-complete: given natural numbers <span class="math-container">$a,b,c$</span>, determine whether there exists a natural number <span class="math-container">$x\le c$</span> such that <span class="math-container">$x^2\equiv a\pmod b$</span>.</p>
<p>NB: <span class="math-container">$0$</span> is a natural number.</p>
<p>The problem can be equivalently stated as follows: given <span class="math-container">$b,c\in\mathbb N$</span>, determine whether the quadratic <span class="math-container">$x^2+by-c=0$</span> has a solution <span class="math-container">$x,y\in\mathbb N$</span>.</p>
<p>[The original paper states the problem with <span class="math-container">$ax^2+by-c$</span>, but it is not hard to see that one can reduce it to the case <span class="math-container">$a=1$</span>.</p>
<p>For the record, the reduction of the first problem to the second one is as follows: given <span class="math-container">$a,b,c\in\mathbb N$</span>, <span class="math-container">$b&gt;0$</span>, let <span class="math-container">$c'\le c^2$</span> be maximal such that <span class="math-container">$c'\equiv a\pmod b$</span>, i.e., <span class="math-container">$c'=a+b\lfloor(c^2-a)/b\rfloor$</span>. If <span class="math-container">$c'&lt;0$</span>, the congruence <span class="math-container">$x^2\equiv a\pmod b$</span> has no solution with <span class="math-container">$0\le x\le c$</span>. Otherwise, it has such a solution iff there are solutions <span class="math-container">$x,y\ge0$</span> to <span class="math-container">$x^2+by-c'=0$</span>.]</p>
<p>[While we are at it, here is a reduction of solvability in <span class="math-container">$\mathbb N$</span> of the more general equations <span class="math-container">$ax^2+by-c=0$</span> (where <span class="math-container">$a,b,c\in\mathbb N$</span>) to the first problem. Let <span class="math-container">$d=\gcd(a,b)$</span>. If <span class="math-container">$d\nmid c$</span>, the problem has no solution even in <span class="math-container">$\mathbb Z$</span>. Otherwise, we can divide out <span class="math-container">$d$</span>, hence we may assume <span class="math-container">$\gcd(a,b)=1$</span>. Then <span class="math-container">$ax^2+by-c=0$</span> has a solution with <span class="math-container">$x,y\ge0$</span> iff <span class="math-container">$x^2\equiv a^{-1}c\pmod b$</span> has a solution with <span class="math-container">$0\le x\le\lfloor\sqrt{c/a}\rfloor$</span>.]</p>

CC BY-SA 4.0
2022-11-29T14:44:25.817Z
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
CC BY-SA 4.0
2024-04-24T04:53:13.117Z
Isn't there a mistake in your equivalent statement? It seems to me that it would reduce to modular SQUARE ROOT.
domotorp
CC BY-SA 4.0
2024-04-24T06:36:36.737Z
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).
Emil Jeřábek
CC BY-SA 4.0
2024-04-24T11:08:27.097Z
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$.
domotorp
CC BY-SA 4.0
2024-04-24T11:49:21.640Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2024-04-24T12:04:08.443Z
Oh, this was the reduction the other way! Of course, you are right.
domotorp
CC BY-SA 4.0
2012-10-31T11:40:35.000Z
2024-04-24T10:17:00.397Z
2024-04-24T10:17:00.397Z
Emil Jeřábek
<p>Here's a  $\text{NEXP}$-complete problem with a single natural number as the input.</p>

<p>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</p>

<blockquote>
  <p>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), <a href="http://dx.doi.org/10.1109/FOCS.2009.22">DOI: 10.1109/FOCS.2009.22</a>. Also <a href="http://arxiv.org/abs/0905.2419">arXiv:0905.2419</a>.</p>
</blockquote>

<p>The problem is defined on page 5 of the arxiv version.</p>

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

CC BY-SA 3.0
2012-10-30T19:30:08.847Z
+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
CC BY-SA 3.0
2012-10-30T19:21:08.387Z
2012-10-30T19:21:08.387Z
Robin Kothari
<p>Our <a href="http://www.math.ucla.edu/~pak/papers/hard_presburger3.pdf" rel="nofollow noreferrer">FOCS'17 paper</a> on the Short Presburger Arithmetic is an example of a "natural" problem which is NP-c, and uses a constant number <span class="math-container">$C$</span> of integers in the input, say <span class="math-container">$C&lt; 220$</span>.  It is different from Manders-Adleman in that the constraints are all inequalities.  See Gil Kalai's <a href="https://gilkalai.wordpress.com/2019/03/22/danny-nguyen-and-igor-pak-presburger-arithmetic-problem-solved/" rel="nofollow noreferrer">blog post</a> for some background.  </p>

CC BY-SA 4.0
2019-05-24T00:04:19.893Z
I think this is more natural than Manders-Adleman. Is smaller than $5$ variables and $10$ inequality example possible?
Turbo
CC BY-SA 4.0
2019-05-24T00:21:25.057Z
No, 5 variables is the smallest.  10 - not sure.  But you can't really have less than 6...
Igor Pak
CC BY-SA 4.0
2019-05-24T00:25:54.507Z
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
CC BY-SA 4.0
2019-05-24T00:28:08.087Z
Yes.  For fewer variables the problem is in P.
Igor Pak
CC BY-SA 4.0
2019-05-24T00:28:33.880Z
Is a reference available for this claim?
Turbo
CC BY-SA 4.0
2019-05-24T00:29:03.540Z
Yes.  It's all in our paper and Danny Nguyen's thesis.  http://www.math.ucla.edu/~pak/papers/Nguyen-thesis.pdf
Igor Pak
CC BY-SA 4.0
2019-05-23T23:20:36.790Z
2019-05-23T23:20:36.790Z
Igor Pak
<p>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?":</p>

<p>Problem: Given $n$, does a Turing machine $M$ exist such that $|M| &lt; 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$</p>

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

CC BY-SA 3.0
2012-10-31T05:50:14.680Z
I think this problem is quite TM based but of course it is impossible to draw a line.
domotorp
CC BY-SA 3.0
2012-10-31T15:36:25.753Z
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
CC BY-SA 3.0
2012-10-30T20:08:31.050Z
2012-10-30T20:22:39.223Z
2012-10-30T20:22:39.223Z
Marzio De Biasi
<p>How about the <a href="http://en.wikipedia.org/wiki/Partition_problem" rel="nofollow">PARTITION problem</a>?</p>

CC BY-SA 3.0
2012-10-31T05:45:53.613Z
No, as the input is not a number but a set.
domotorp
CC BY-SA 3.0
2012-10-31T13:06:20.527Z
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
CC BY-SA 3.0
2012-10-31T13:20:44.407Z
I am sorry if I was vague in the formulation of the question.
domotorp
CC BY-SA 3.0
2012-10-31T04:12:24.733Z
2012-10-31T04:12:24.733Z
Kevin A. Wortman
<p>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 &quot;Is n a prime?&quot; is such a natural problem, but this one is in P. Or &quot;Who wins the Nim game with heaps of size 3, 5, n, n?&quot; 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.</p>
<p>Update: As pointed out by Emil Jeřábek, given <span class="math-container">$a,b,c\in \mathbb N,$</span> to determine whether <span class="math-container">$ax^2+by-c=0$</span> 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.</p>

CC BY-SA 3.0
2012-10-30T16:04:08.583Z
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
CC BY-SA 3.0
2012-10-30T17:40:11.323Z
What about problems like subset sum? The input is a set of integers, similar to your nim example.
Evgenij Thorstensen
CC BY-SA 3.0
2012-10-30T17:40:16.773Z
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
CC BY-SA 3.0
2012-10-30T18:55:02.450Z
@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
CC BY-SA 3.0
2012-10-30T18:56:06.800Z
@Robin: Yes, I would be very much interested in the NEXP-complete tiling thing.
domotorp
CC BY-SA 3.0
2012-10-30T18:57:06.580Z
@Evgenij: I want the input to be only one integer, similar to my nim example.
domotorp
CC BY-SA 3.0
2012-10-30T19:03:20.183Z
@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
CC BY-SA 3.0
2012-10-31T04:44:03.217Z
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ε
CC BY-SA 3.0
2012-10-31T14:12:13.577Z
@JɛﬀE: 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
CC BY-SA 3.0
2012-10-31T14:48:49.890Z
@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](http://ww1.ucmss.com/books/LFS/CSREA2006/CSC4596.pdf): "... 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
CC BY-SA 3.0
2012-11-02T18:56:55.160Z
similar question/answers on mathoverflow here [Number theory and NP-complete](http://mathoverflow.net/questions/72628/number-theory-and-np-complete)
vzn
<cc.complexity-theory><np-hardness><nt.number-theory><combinatorial-game-theory>
Is there a natural problem on the naturals that is NP-complete?
domotorp
# Is there a natural problem on the naturals that is NP-complete?

(Asked by: username_0 on 2012-10-30)

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.

**Tags:** cc.complexity-theory, np-hardness, nt.number-theory, combinatorial-game-theory
> **Comments:**
> **username_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.  
> **username_2**: What about problems like subset sum? The input is a set of integers, similar to your nim example.  
> **username_3**: 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.  
> **username_0**: @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.  
> **username_0**: @Robin: Yes, I would be very much interested in the NEXP-complete tiling thing.  
> **username_0**: @Evgenij: I want the input to be only one integer, similar to my nim example.  
> **username_3**: @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 .)  
> **username_4**: 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!  
> **username_5**: @JɛﬀE: 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.  
> **username_6**: @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](http://ww1.ucmss.com/books/LFS/CSREA2006/CSC4596.pdf): "... 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 ..."  
> **username_7**: similar question/answers on mathoverflow here [Number theory and NP-complete](http://mathoverflow.net/questions/72628/number-theory-and-np-complete)  

---

## 5 answers

### Answer by username_3 on 2012-10-31. Score: 36

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

As proved by [Manders and Adleman](http://dx.doi.org/10.1145/800113.803627), 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$.]

> **Comments:**
> **username_8**: 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!  
> **username_0**: Isn't there a mistake in your equivalent statement? It seems to me that it would reduce to modular SQUARE ROOT.  
> **username_3**: 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).  
> **username_0**: 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$.  
> **username_3**: 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$.  
> **username_0**: Oh, this was the reduction the other way! Of course, you are right.  

---

### Answer by username_1 on 2012-10-30. Score: 12

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](http://dx.doi.org/10.1109/FOCS.2009.22). Also [arXiv:0905.2419](http://arxiv.org/abs/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}$.)

> **Comments:**
> **username_9**: +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.  

---

### Answer by username_10 on 2019-05-23. Score: 2

Our [FOCS'17 paper](http://www.math.ucla.edu/~pak/papers/hard_presburger3.pdf) 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](https://gilkalai.wordpress.com/2019/03/22/danny-nguyen-and-igor-pak-presburger-arithmetic-problem-solved/) for some background.

> **Comments:**
> **username_11**: I think this is more natural than Manders-Adleman. Is smaller than $5$ variables and $10$ inequality example possible?  
> **username_10**: No, 5 variables is the smallest.  10 - not sure.  But you can't really have less than 6...  
> **username_11**: 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$?)?  
> **username_10**: Yes.  For fewer variables the problem is in P.  
> **username_11**: Is a reference available for this claim?  
> **username_10**: Yes.  It's all in our paper and Danny Nguyen's thesis.  http://www.math.ucla.edu/~pak/papers/Nguyen-thesis.pdf  

---

### Answer by username_6 on 2012-10-30. Score: 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$.

> **Comments:**
> **username_0**: I think this problem is quite TM based but of course it is impossible to draw a line.  
> **username_5**: 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.)  

---

### Answer by username_12 on 2012-10-31. Score: 1

How about the [PARTITION problem](http://en.wikipedia.org/wiki/Partition_problem)?

> **Comments:**
> **username_0**: No, as the input is not a number but a set.  
> **username_12**: 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.  
> **username_0**: I am sorry if I was vague in the formulation of the question.  

---

