This question is a generalized variant of: Hardness of perimeter minimization?

Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded in binary.

What is the complexity of finding $x, y, z$ such that $xy+xz+yz$ has minimum value? Is there any subexponential algorithm that solves this problem? Does the problem become easier when integers are encoded in unary?

Edit Motivation: I'm interested in the following generalized problem:

Input: intgers $C$ and $K$

Problem: Find integers $x$, $y$, and $z$ such that $xyz\ge C$ and $xy+xz+yz\le K$

  • 1
    $\begingroup$ Are we given the factorization of $C$? That's probably the hardest part. $\endgroup$ – Peter Shor Nov 10 '10 at 13:51
  • $\begingroup$ @Peter, No. By the way, Am I right in assuming that your Quantum factoring algorithm solves the 2D case in polynomial-time? Is there an efficient quantum algorithm for this 3D problem? $\endgroup$ – Mohammad Al-Turkistany Nov 10 '10 at 14:13
  • $\begingroup$ The quantum factoring algorithm factors any integer efficiently, including products of 3 primes. $\endgroup$ – Peter Shor Nov 10 '10 at 14:37
  • $\begingroup$ @Peter, Thanks a lot for your prompt answers. $\endgroup$ – Mohammad Al-Turkistany Nov 10 '10 at 14:45

Never mind. I misremembered the definition of 3-partition.

I'll leave what I wrote here here, but since division into 3 subsets with equal sums is not strongly NP-complete, this doesn't work.

By 3-subset sum, I mean a: given a set of integers, find a partition into 3 subsets whose sums are all equal.

The problem is roughly equivalent to: let $\{p_i\}$ be the multiset of prime factors of $C$; find the best way of partitioning the multiset $\{r_i\}$ into three parts with equal sums, where $r_i = \log p_i$, for $p_i$.

Here's the wrong argument I had before.


Find a bunch of primes $p_1$, $p_2$, $\ldots$, $p_{\alpha(n)}$ so that $\log p_i \approx M\ i$ for some real $M$. Now, take a 3-subset sum problem on integers $1 \ldots \alpha(n)$, and replace the integer $i$ with prime $p_i$. Let $C$ be the product of all the primes $p_i$ corresponding to the integers $i$ in the 3-subset sum problem. Then, any $x$, $y$, $z$ with $x \approx y \approx z$ and $xyz = C$ gives a good partition of the integers in the 3-subset sum problem. Let $p_x$, $p_y$, and $p_z$ be the multisets of primes making up the prime factorization of $x$, $y$, and $z$, respectively. If $x$, $y$, and $z$ are close, $\log x \approx \log y \approx \log z$ means $ \sum_{p_i \in p_x} \log p_i \approx \sum_{p_i \in p_y} \log p_i \approx \sum_{p_i \in p_z} \log p_i$, and so you have a good solution to the 3-subset sum problem (and if you've chosen the primes right, you can tell from the optimal $x$, $y$ and $z$ whether or not the original 3-subset-sum problem is solvable). Since you know what the primes you used were, factoring $x$, $y$ and $z$ can be done by trial division to recover the partition.

  • $\begingroup$ Thanks Peter for your answer. I failed to mention that $x$, $y$, and $z$ are prime numbers. Does this change the problem's complexity? $\endgroup$ – Mohammad Al-Turkistany Nov 10 '10 at 14:22
  • 2
    $\begingroup$ If $x$, $y$ and $z$ are prime numbers, then there is only one way of decomposing $C$ into three numbers larger than 1 so that $xyz = C$, and that is the answer (since if one of these numbers is 1, the area is at least $C$). So the problem reduces to that of factoring $C$. For classical algorithms, I don't believe the complexity factoring $C$ is reduced much if you know it has 3 factors and not 2. $\endgroup$ – Peter Shor Nov 10 '10 at 14:38
  • $\begingroup$ @Peter, Could you please provide a reference for this version of 3-partition problem? $\endgroup$ – Mohammad Al-Turkistany Nov 10 '10 at 15:53
  • 1
    $\begingroup$ @Peter, it's not entirely clear to me how you do this. I can understand a mapping from the elements of the instance of 3-PARTITION to specific primes, but it's not clear how you enforce that the A,B,D partition induced by the log p_is translates back to a valid partition for the original inputs. $\endgroup$ – Suresh Venkat Nov 10 '10 at 16:34
  • $\begingroup$ @Suresh: Looking over my answer, I see that this would be a completely inadequate answer on a graduate problem set, even though it contains the right ideas. Let me edit it. $\endgroup$ – Peter Shor Nov 10 '10 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.