12
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/40990/5038, math.stackexchange.com/q/2813909/14578. 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$ 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$? $\endgroup$ – Steven Stadnicki Jun 15 '18 at 19:34
  • 2
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Jun 16 '18 at 16:25
  • 6
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Jun 18 '18 at 8:16
  • 2
    $\begingroup$ Related: It's shown in "NP-Complete Decision Problems for Quadratic Polynomials" by Manders and Adelman (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$. $\endgroup$ – GMB Jul 26 '18 at 17:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.