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.

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
  • 7
    $\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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.