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?


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.


closed as off-topic by quid Jul 26 '18 at 13:11

  • This question does not appear to be about math within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I have added this question here: cstheory.stackexchange.com/questions/40990/… $\endgroup$ – Mason Jun 13 '18 at 23:00
  • 1
    $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Jun 14 '18 at 7:42
  • $\begingroup$ Thanks @D.W. I will be more cautious in the future. I am still getting a feel for which community is interested in what content. What do you suggest to do about the situation now? I think the question was better received cstheory.se but have already used my precious reputation to start a bounty here. I think I would like one of the question to be "closed" or put "on hold" while the other community takes a crack at it. I think it's best if it's "on hold" on Math.SE. and has a link to the CSTheory.SE $\endgroup$ – Mason Jun 14 '18 at 10:14
  • $\begingroup$ At @D.W. I flagged the question asking for moderation. $\endgroup$ – Mason Jun 14 '18 at 10:21
  • $\begingroup$ How does this relate to Hilbert's 10th problem? en.wikipedia.org/wiki/Hilbert%27s_tenth_problem $\endgroup$ – Mason Jun 17 '18 at 2:54