2
$\begingroup$

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$

$\endgroup$
4
  • 1
    $\begingroup$ Are we given the factorization of $C$? That's probably the hardest part. $\endgroup$ Nov 10, 2010 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$ Nov 10, 2010 at 14:13
  • $\begingroup$ The quantum factoring algorithm factors any integer efficiently, including products of 3 primes. $\endgroup$ Nov 10, 2010 at 14:37
  • $\begingroup$ @Peter, Thanks a lot for your prompt answers. $\endgroup$ Nov 10, 2010 at 14:45

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
8
  • $\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$ Nov 10, 2010 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$ Nov 10, 2010 at 14:38
  • $\begingroup$ @Peter, Could you please provide a reference for this version of 3-partition problem? $\endgroup$ Nov 10, 2010 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$ Nov 10, 2010 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$ Nov 10, 2010 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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