<p><strong>Question</strong></p>

<p>I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete. </p>

<p>Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$. </p>

<p>Where $\bar{x}=(x_1,x_2,\dots x_n)$ and $\bar{y}=(y_1,y_2,\dots y_n)$ are tuples of non-negative integers. </p>

<p>How long does it take to "decide" whether a given $(\bar{w},r)$  is in the "language" $L$? This is obviously in NP but is it NP-Complete remains to be concluded. Is this language NP-Complete? </p>

<p><strong>Motivations</strong> </p>

<p>This problem comes out of my own explorations. I have been exploring solutions on hyperspheres and this is a natural generalization of a hypersphere. 
Note that $(&lt;2,2,2,2,2,2&gt;, 296675)\in L$ because by Lagrange we know that there exists some $(x_1,x_2,x_3,x_4,x_5,x_6)$ which satisfies 
$x_1^2+x_2^2+x_3^2+x_4^2+x_5^2+x_6^2=296675$. An $n&gt;3$ dimensional hypersphere with radius $\sqrt{r}$, where $r$ is a whole number centered at the origin can always be satisfied by some integer coordinates (Lagrange's sum of 4 squares theorem). This makes the "decision" problem easy. There IS some solution though it might be hard to find.  </p>

<p>But what about 
$x_1^2+x_2^3+x_3^4+x_4^5+x_5^6+x_6^7=296675$?</p>

<p>"Is there a solution to the equation above?" is the same as "Is $(&lt;2,3,4,5,6,7&gt;,296675) \in L$?" in my notation above. </p>

<p>This may be a computationally tricky problem to solve. I know of no guarantee that there must be some $(x_1,x_2,x_3,x_4,x_5,x_6)$ which satisfies the equation. On the otherhand, given an "instance" $(x_1,x_2,x_3,x_4,x_5,x_6)=(1,2,3,4,5,6)$ this problem is easy to verify. "Hard to solve but easy to verify" is a hallmark of NP problems.</p>

CC BY-SA 4.0
2018-06-14T07:42:15.583Z
Cross-posted: https://cstheory.stackexchange.com/q/40990/5038, https://math.stackexchange.com/q/2813909/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.
D.W.
CC BY-SA 4.0
2018-06-15T19:34:49.100Z
Important correction: $r$ should be part of your instance size. It seems like you've already considered this, but you should be explicit about whether your instances are 'unary' or 'binary'; i.e., is your instance size $r+\sum_i y_i$, or $\lg r+\sum_i \lg y_i$?
Steven Stadnicki
CC BY-SA 4.0
2018-06-16T16:25:07.733Z
It does not matter at all if you write the $y_i$ in unary or in binary. Once $y_i>\log_2r$, the only possible solutions are with $x_i=0$ or $x_i=1$, in which case the exact value of $y_i$ makes no difference. Thus you can assume without loss of generality $y_i\le\log_2r+1$.
Emil Jeřábek
CC BY-SA 4.0
2018-06-18T08:16:12.110Z
While I don’t know how to show full NP-hardness, the problem should not be efficiently solvable. Already in the special case $n=2$, $y_1=y_2=2$, the problem asks whether a given $r$ is a sum of two squares. The answer is YES iff every prime $p\equiv3\pmod4$ occurs in the prime factorization of $r$ with even multiplicity, and there is no known algorithm  that would check it faster than by factoring $r$.
Emil Jeřábek
CC BY-SA 4.0
2018-07-26T17:04:11.043Z
Related: It's shown in "NP-Complete Decision Problems for Quadratic Polynomials" by Manders and Adelman (https://dl.acm.org/citation.cfm?id=803627) that the following problem is NP Complete: given naturals $a, b, r$ on input, decide whether or not there exist naturals $x_1, x_2$ such that $ax_1^2 + bx_2 = r$.
GMB
CC BY-SA 4.0
2018-07-27T00:59:37.533Z
@GMB. Thanks! A discussion of that can be found here: https://mathoverflow.net/questions/36420/is-the-solution-bounded-diophantine-problem-np-complete
Mason
CC BY-SA 4.0
2018-07-27T01:14:42.740Z
Warning: this may very well be red-herring: In a not so tangential way this question can be re-framed as asking about computing the coefficients of the products of theta series. I have laid this out: here[https://math.stackexchange.com/questions/2837316/whats-the-connection-between-theta-series-and-the-number-of-integer-solution].
Mason
<np-complete><np><subset-sum><sum-of-squares>
Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?
Mason
# Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?

(Asked by: username_0 on 2018-06-13)

**Question**

I would like to show that satisfying $\sum\_{i=1}^{n}{x\_i^{y\_i}}=r$ is NP-Complete.

Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum\_{i=1}^{n}{x\_i^{y\_i}}=r\}$.

Where $\bar{x}=(x\_1,x\_2,\dots x\_n)$ and $\bar{y}=(y\_1,y\_2,\dots y\_n)$ are tuples of non-negative integers.

How long does it take to "decide" whether a given $(\bar{w},r)$ is in the "language" $L$? This is obviously in NP but is it NP-Complete remains to be concluded. Is this language NP-Complete?

**Motivations**

This problem comes out of my own explorations. I have been exploring solutions on hyperspheres and this is a natural generalization of a hypersphere.
Note that $(<2,2,2,2,2,2>, 296675)\in L$ because by Lagrange we know that there exists some $(x\_1,x\_2,x\_3,x\_4,x\_5,x\_6)$ which satisfies
$x\_1^2+x\_2^2+x\_3^2+x\_4^2+x\_5^2+x\_6^2=296675$. An $n>3$ dimensional hypersphere with radius $\sqrt{r}$, where $r$ is a whole number centered at the origin can always be satisfied by some integer coordinates (Lagrange's sum of 4 squares theorem). This makes the "decision" problem easy. There IS some solution though it might be hard to find.

But what about
$x\_1^2+x\_2^3+x\_3^4+x\_4^5+x\_5^6+x\_6^7=296675$?

"Is there a solution to the equation above?" is the same as "Is $(<2,3,4,5,6,7>,296675) \in L$?" in my notation above.

This may be a computationally tricky problem to solve. I know of no guarantee that there must be some $(x\_1,x\_2,x\_3,x\_4,x\_5,x\_6)$ which satisfies the equation. On the otherhand, given an "instance" $(x\_1,x\_2,x\_3,x\_4,x\_5,x\_6)=(1,2,3,4,5,6)$ this problem is easy to verify. "Hard to solve but easy to verify" is a hallmark of NP problems.

**Tags:** np-complete, np, subset-sum, sum-of-squares
> **Comments:**
> **username_1**: Cross-posted: https://cstheory.stackexchange.com/q/40990/5038, https://math.stackexchange.com/q/2813909/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.  
> **username_2**: Important correction: $r$ should be part of your instance size. It seems like you've already considered this, but you should be explicit about whether your instances are 'unary' or 'binary'; i.e., is your instance size $r+\sum_i y_i$, or $\lg r+\sum_i \lg y_i$?  
> **username_3**: It does not matter at all if you write the $y_i$ in unary or in binary. Once $y_i>\log_2r$, the only possible solutions are with $x_i=0$ or $x_i=1$, in which case the exact value of $y_i$ makes no difference. Thus you can assume without loss of generality $y_i\le\log_2r+1$.  
> **username_3**: While I don’t know how to show full NP-hardness, the problem should not be efficiently solvable. Already in the special case $n=2$, $y_1=y_2=2$, the problem asks whether a given $r$ is a sum of two squares. The answer is YES iff every prime $p\equiv3\pmod4$ occurs in the prime factorization of $r$ with even multiplicity, and there is no known algorithm  that would check it faster than by factoring $r$.  
> **username_4**: Related: It's shown in "NP-Complete Decision Problems for Quadratic Polynomials" by Manders and Adelman (https://dl.acm.org/citation.cfm?id=803627) that the following problem is NP Complete: given naturals $a, b, r$ on input, decide whether or not there exist naturals $x_1, x_2$ such that $ax_1^2 + bx_2 = r$.  
> **username_0**: @GMB. Thanks! A discussion of that can be found here: https://mathoverflow.net/questions/36420/is-the-solution-bounded-diophantine-problem-np-complete  
> **username_0**: Warning: this may very well be red-herring: In a not so tangential way this question can be re-framed as asking about computing the coefficients of the products of theta series. I have laid this out: here[https://math.stackexchange.com/questions/2837316/whats-the-connection-between-theta-series-and-the-number-of-integer-solution].  

---

## 0 answers

