<p>Never mind. I misremembered the definition of 3-partition.</p>

<p>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.</p>

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

<p>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$.</p>

<p>Here's the wrong argument I had before.</p>

<p>=========================</p>

<p>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. </p>

CC BY-SA 2.5
2010-11-10T14:22:13.363Z
Thanks Peter for your answer. I failed to mention that $x$, $y$, and $z$ are prime numbers. Does this change the problem's complexity?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-10T14:38:57.530Z
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.
Peter Shor 
CC BY-SA 2.5
2010-11-10T15:53:19.193Z
@Peter, Could you please provide a reference for this version of 3-partition problem?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-10T16:34:04.053Z
@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.
Suresh Venkat
CC BY-SA 2.5
2010-11-10T16:45:34.527Z
@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.
Peter Shor 
CC BY-SA 2.5
2010-11-10T18:00:36.450Z
ah ok. I see now. is the log p_i = Mi step the place where you need the number-theoretic assumptions ?
Suresh Venkat
CC BY-SA 2.5
2010-11-10T18:30:11.437Z
@Suresh: It is.
Peter Shor 
CC BY-SA 2.5
2010-11-11T02:01:43.050Z
@Suresh: I misremembered the definition of 3-partition. The problem naturally is equivalent to a subset-sum problem which isn't strongly NP-complete (and in fact, dynamic programming can approximate it well). So the question is still open.
Peter Shor 
CC BY-SA 2.5
2010-11-10T14:04:20.423Z
2010-11-10T23:13:49.927Z
2010-11-10T23:13:49.927Z
Peter Shor 
<p>This question is a generalized variant of: <a href="https://math.stackexchange.com/questions/9541/hardness-of-perimeter-minimization">Hardness of perimeter minimization?</a>
<a href="https://math.stackexchange.com/questions/9541/hardness-of-perimeter-minimization"></a></p>

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

<blockquote>
  <p>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?</p>
</blockquote>

<p><strong>Edit</strong> Motivation: I'm interested in the following generalized problem:</p>

<p><strong>Input</strong>: intgers $C$ and $K$</p>

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

CC BY-SA 2.5
2010-11-10T13:51:34.973Z
Are we given the factorization of $C$? That's probably the hardest part.
Peter Shor 
CC BY-SA 2.5
2010-11-10T14:13:40.020Z
@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?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-10T14:37:34.440Z
The quantum factoring algorithm factors any integer efficiently, including products of 3 primes.
Peter Shor 
CC BY-SA 2.5
2010-11-10T14:45:52.680Z
@Peter, Thanks a lot for your prompt answers.
Mohammad Al-Turkistany
<cc.complexity-theory>
Hardness of geometric area minimization problem
Mohammad Al-Turkistany
# Hardness of geometric area minimization problem

(Asked by: username_0 on 2010-11-10)

This question is a generalized variant of: [Hardness of perimeter minimization?](https://math.stackexchange.com/questions/9541/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$

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Are we given the factorization of $C$? That's probably the hardest part.  
> **username_0**: @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?  
> **username_1**: The quantum factoring algorithm factors any integer efficiently, including products of 3 primes.  
> **username_0**: @Peter, Thanks a lot for your prompt answers.  

---

## 1 answers

### Answer by username_1 on 2010-11-10. Score: 6

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.

> **Comments:**
> **username_0**: Thanks Peter for your answer. I failed to mention that $x$, $y$, and $z$ are prime numbers. Does this change the problem's complexity?  
> **username_1**: 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.  
> **username_0**: @Peter, Could you please provide a reference for this version of 3-partition problem?  
> **username_2**: @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.  
> **username_1**: @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.  
> **username_2**: ah ok. I see now. is the log p_i = Mi step the place where you need the number-theoretic assumptions ?  
> **username_1**: @Suresh: It is.  
> **username_1**: @Suresh: I misremembered the definition of 3-partition. The problem naturally is equivalent to a subset-sum problem which isn't strongly NP-complete (and in fact, dynamic programming can approximate it well). So the question is still open.  

---

