# Hardness of geometric area minimization problem

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$

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

• Thanks Peter for your answer. I failed to mention that $x$, $y$, and $z$ are prime numbers. Does this change the problem's complexity? Nov 10, 2010 at 14:22
• 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. Nov 10, 2010 at 14:38
• @Peter, Could you please provide a reference for this version of 3-partition problem? Nov 10, 2010 at 15:53
• @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. Nov 10, 2010 at 16:34
• @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. Nov 10, 2010 at 16:45