21
$\begingroup$

Consider the following algorithmic task:

Input: a positive integer $n$, along with its prime factorization
Find: positive integers $x,y,z$ that minimize $xy+yz+xz$, subject to the restriction that $xyz=n$

What is the complexity of this problem? Is there a polynomial-time algorithm? Is it NP-hard?


This problem basically asks: out of all rectangular solids whose volume is $n$ and whose dimensions are all integers, which one has the least surface area?

This problem was posed by Dan Meyer, under the title The Math Problem That 1,000 Math Teachers Couldn’t Solve. So far none of the math teachers he worked with has found a reasonable algorithm for this problem. In his context, the definition of "reasonable" is a bit imprecise, but as computer scientists we can ask a more precise question about the complexity of this problem.

The obvious approach is to enumerate all possibilities for $x,y,z$, but that takes exponential time. Commenters at Dan Meyer's blog have proposed many efficient candidate algorithms that unfortunately all turned out to be incorrect. Martin Strauss suggests that this problem seems vaguely reminiscent of 3-partition, but I can't see a reduction.


Let me also clear up some misconceptions that I've seen in the comments/answers:

  • You can't reduce from 3-partition by simply replacing each number $q$ with its power $2^q$, as the objective functions of the two problems are different. The obvious reduction simply doesn't work.

  • It is not true that the optimal solution involves picking one of $x,y,z$ to be the nearest divisor of $n$ to $\sqrt[3]{n}$. I see multiple people who are assuming this is case, but in fact, that is not correct. This has already been disproven on the Dan Meyer blog post. For instance, consider $n=68$; $\sqrt[3]{68} \approx 4$, and 4 divides 68, so you might think that at least one of $x,y,z$ should be 4; however, that is not correct. The optimal solution is $x=2$, $y=2$, $z=17$. Another counterexample is $n=222$, $\sqrt[3]{222}\approx 6$, but the optimal solution is $x=37$, $y=3$, $z=2$. (It might be true that for all $n$, the optimal solution involves making at least one of $x,y,z$ be equal to either the smallest divisor of $n$ larger than $\sqrt[3]{n}$ or the largest divisor of $n$ smaller than $\sqrt[3]{n}$ -- I don't have a counterexample right now -- but if you think this statement is true, it would need proof. You absolutely cannot assume it is true.)

  • "Make $x,y,z$ be the same size" does not appear to necessarily yield the optimal answer in all cases; see Dan Meyer's blog post for counterexamples. Or, at least, for some reasonable interpretations of the phrase "make them roughly the same size", there are counterexamples showing that this strategy is not in fact optimal. If you want to try some strategy of that sort, make sure that you state the claim precisely and then provide a careful mathematical proof.

  • A running time of $O(n^3)$ is not polynomial. For this problem to be in P, the running time must be a polynomial in the length of the input. The length of the input is something like $\lg n$, not $n$. The obvious brute-force algorithm can be made to run in $O(n^3)$ or $O(n^2)$ time, but that is exponential in $\lg n$ and thus counts as an exponential-time algorithm. Thus that is not helpful.

$\endgroup$
  • 1
    $\begingroup$ Interesting. My naive approach would be "make $x,y,z$ roughly the same size", generalizing the idea that the cube is the rectangular solid with the smallest surface area for a given volume. Would that work? And if so: I don't see how to do that efficiently, but is there a reduction that's easier to attain, maybe? $\endgroup$ – G. Bach Sep 28 '15 at 10:57
  • 2
    $\begingroup$ A reduction is going to be a nightmare since you need a way to generate suitable prime numbers. The best you could hope for is a randomized reduction, using something like Dirichlet's Theorem to generate suitable primes but even that seems unlikely. $\endgroup$ – Tom van der Zanden Sep 28 '15 at 12:10
  • 1
    $\begingroup$ @G.Bach, I think that blog article considers a bunch of heuristics of that vein (e.g., start with each of $x,y,z$ to be the nearest integer to $\sqrt[3]{n}$ and then adjust them a tiny bit), and shows explicit counterexamples for each. But maybe you have an algorithm that they haven't considered? $\endgroup$ – D.W. Sep 28 '15 at 14:19
  • 3
    $\begingroup$ oeis.org/A075777 seems to claim an algorithm, but it appears to be incorect (n=1332 generates 9,4,37 instead of 6,6,37 for example) $\endgroup$ – Scott Farrar Sep 29 '15 at 16:53
  • 1
    $\begingroup$ Here's an observation that may be useful. Given $x$, the optimal $y,z$ do in fact satisfy the "naive dream": they must be the pair of factors of $n/x$ closest to $\sqrt{n/x}$. (This is easy to prove.) At an optimal solution $x^*,y^*,z^*$, this condition must hold for all three variables simultaneously: $x^*,y^*$ are the pair corresponding to $z^*$, etc. One implication: given $z$, there is only one possible pair $x,y$ with which it can be optimal. Unfortunately, (1) this condition does not uniquely identify the optimal triple; (2) I don't see how to find the corresponding pair fast. $\endgroup$ – usul Oct 10 '15 at 19:39
1
$\begingroup$

Here is a modified version of a "choose divisor near cube root" algorithm. It still must brute force many cases, so I'm not sure how much of a real improvement it is speed wise over the enumeration of all cases. However, I submitted it as a correction to the algorithm on OEIS (that which generated incorrect results) because I believe it should be accurate at least.

Here is the algorithm to find (s1,s2,s3) and surface area of a rectangular prism given its volume n:

  1. Given n, find the cube root.
  2. Set an initial value integer s1 at the ceiling of that cube root.
  3. Test to see if s1 is a divisor of n, and if not, reduce s1 by 1.
  4. If a divisor s1 is found, set an initial s2 to be the ceiling of the square root of (n/s1).
  5. Then test to see if s2 is a divisor of n/s1, and if not, reduce s2 by 1.
  6. When a divisor s2 is found, s3 then is set to n/(s1*s2).
  7. The current surface area is calculated by 2*(s1*s2 + s1*s3 + s2*s3).
  8. The current SA is compared against the current minimum. If its the first surface area calculated, it is stored as minSA. After the first, we test to see if the current SA is smaller than minSA, and if so, store it in minSA.

This algorithm enumerates some of the triples (s1,s2,s3) but needs only to test the divisors under the cube root. (Since not all three divisors can be above the cube root). In a similar fashion, s2 needs only to test divisors of n/s1 under the square root of n/s1, since not both divisors can be above the square root)

A note on step 3: if the cube root is a divisor then n is a cube and we can stop there with minimal surface area 6*s1^2 from the box (s1,s1,s1).

Python:

import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0))) 
    minSA=-1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:  
            s1 = s1 - 1
        s1quot = int(n/s1) 
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))  
            SA = 2*(s1*s2 + s1*s3 + s2*s3)  
            if minSA==-1:
                minSA=SA
            else:
                if SA<minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1    
    return minSA
$\endgroup$
  • $\begingroup$ Your algorithm takes exponential time. Each loop examines about $\sqrt[3]{n}$ possible candidates, so the running time is $O(\sqrt[3]{n}^2) = O(n^{2/3})$, which is exponential, not polynomial time. Thus, this algorithm doesn't answer the question. (I already mentioned an exponential-time algorithm in the question.) $\endgroup$ – D.W. Sep 30 '15 at 18:03
  • $\begingroup$ Hmm, y is not confined under the cube root of n, for example, n=1332, we will eventually test s1=2, meaning s2 will be under the square root of 1332/2 ~= 26. Indeed (2,18,37) is tested with y and z above the cube root. $\endgroup$ – Scott Farrar Sep 30 '15 at 18:12
  • $\begingroup$ @ScottFarrar, yes, I know. I did not include all the gory details of the complexity analysis; there wasn't space in a single comment. If you do include the gory details, I think you'll find that you get the running time I quoted. You can either trust me :-), or read our reference question to learn more about those gory details. In any case, even if you removed the inner loop, the outer loop still does $\Theta(n^{1/3})$ iterations, so the running time of your algorithm is at least $\Omega(n^{1/3})$ -- i.e., it is certainly exponential. $\endgroup$ – D.W. Sep 30 '15 at 18:33
0
$\begingroup$

The problem would of course be related to factoring complexity if prime decompositions were not given. Given the factors, and taking logs of all the prime factors, this problem appears to be about the same as minimizing the deviation-from-mean of $k$ partition sums (exercise, maybe either analytically or experimentally, find how closely this intuitive approximation of the problem holds).

Here this is the 3-way case (partition sums are $\log(x), \log(y), \log(z)$). the 2-way case has been extensively studied and is NP hard (from 1st ref). (This 2-way case is not quite the same as the known NP-complete 2-way Partition problem where partition sums are equal. Note equal partition sums implies 0 deviation in partition sums and vice versa.) The 2nd ref studies 3-way and $n$-way partitioning, partly empirically, where there is not as much study as the 2-way case.

$\endgroup$
  • $\begingroup$ This answer is not helpful and does not answer the question. 1. I am looking for proofs or evidence, not speculation. There is no evidence that minimizing deviation yields an optimal solution. Even if that were true, it wouldn't answer the question: it would not tell us the complexity of minimizing the deviation. 2. The first reference is about 2-partition. Pointing me to a reference on 2-partition is not helpful. I already explained in the question why my problem is not just 3-partition (or 2-partition). A paper on a variant of a problem that I didn't ask about isn't helpful. $\endgroup$ – D.W. Sep 30 '15 at 5:41
  • $\begingroup$ Counterexample to the claim that you should minimize the absolute deviation from the mean: $n=68$. Then $1,4,17$ yields an absolute deviation of $2.85342$, which is the lowest possible absolute deviation. However $2,2,17$ is the correct (optimal) solution, and has smaller surface area. [By absolute deviation from the mean, I specifically mean $|\log(x)-\mu|+|\log(y)-\mu|+|\log(z)-\mu|$ (where $\mu=(\log(x)+\log(y)+\log(z))/3$).] $\endgroup$ – D.W. Sep 30 '15 at 6:01
  • $\begingroup$ ok! there was never any claim this algorithm was correct, it was based on inspection of some examples & others suggestions in comments. this is only a single counterexample (you indicated the minimizing deviation method is flawed in the revised post). the question of "how often" this algorithm gives a correct solution is interesting because it could give some clues to a correct optimization metric. conjecture this algorithm "often" gives the correct answer. the 2-way ref is to show a deviation version of the problem which is different than the typical exact version on wikipedia etc $\endgroup$ – vzn Sep 30 '15 at 14:56
  • $\begingroup$ see also Lakatos Proofs and refutations $\endgroup$ – vzn Sep 30 '15 at 15:03
0
$\begingroup$

Edit

Here’s an informal argument for why a fast algorithm is unlikely to exist. That sentence hasn't changed, but I’ve taken out what used to be here because it was structured too much like the formal proof in the next section and the discussion was getting sidetracked onto its bugs, some of which I noticed myself and one of which D.W. kindly pointed out to me. Let me instead try to express the intuition behind it.

The clever approaches to this problem seem to be focusing on finding ways to partition the prime factors of $N$ into three lists and quickly prune most of the combinations without needing to check them. So suppose this approach works, that is, it gives you a P-time algorithm for finding the optimal box.

What happens when we translate the same steps into a different algebra, such as addition and subtraction instead of multiplication and division? We know (see lemma below) that our algorithm will find a 3-partition whose products are equal, if one exists, or else determine that no such 3-partition exists. So, if we could translate the same techniques into the additive group, we could find a 3-partition whose sums are equal, or determine that no such partition exists. In other words, we could solve 3-partition in polynomial time. That’s not very plausible.

So, why might such an algorithm work for multiplication and fail for addition? One possible reason is that every integer has a unique prime factorization under multiplication, but is cyclic under addition. Another is that multiplication forms a ring with addition, so you have another set of operations you can use. Another is that you would have to generalize the algorithm to work for non-primes, and it might depend on their primality. The one D.W. pointed out is that the specific method of translation might exponentially increase the size of your inputs. And maybe P = NP after all.

But if those are the loopholes that let a fast algorithm work, I think it’s still useful to know, because it suggests where we should focus our efforts. We should be looking for something that would break if we tried to apply it to a NP-complete problem. An approach that would generalize to other algebras is probably barking up the wrong tree. I suspect, though, that multiplication is not really different enough for that to work, but that’s just a hunch.

Lemma

Let $m = \sqrt[3]{N}$. For any solution $(am, bm, \frac{m}{ab})$, where $a$ and $b$ are positive, the weight of the solution is $(ab + \frac{1}{a} + \frac{1}{b})m^2$ and is minimized when $a = b = 1$.

Proof: We see immediately from the restriction $xyz = N$ that any arbitrary solution has this form.

Its weight is $(am)(bm) + (am)(\frac{m}{ab}) + (bm)(\frac{m}{ab}) = abm^2 + \frac{m^2}{b} + \frac{m^2}{a} = (ab+\frac{1}{a}+\frac{1}{b})m^2$.

Let $f(a,b) = ab + \frac{1}{a} + \frac{1}{b}$. To minimize this function, we take the partial derivatives $\frac{\delta f}{\delta a} = b - \frac{1}{a^2}$ and $\frac{\delta f}{\delta b} = a - \frac{1}{b^2}$. The critical point where these partial derivatives are zero comes where $a = b^2, b = a^2$, and therefore, since $a$ and $b$ must be real numbers greater than 0, $a = b = 1$. We see from the matrix of second-order partial derivatives that this is a global minimum.

My immediate motivation to prove this was to fill in a hand wave in my proof above that, if a perfect-cube solution exists, it is optimal. However, this formula could be useful for pruning the search tree.

Assorted Thoughts

I don’t see any obvious symmetry except the interchangeability of x, y and z, which only gives us at best a constant factor of 6. We do have some speedups for the 2-partition that basically say we’d want both terms to be as close to each other as possible, but I don’t immediately see an application to this problem.

Off the top of my head, simply taking the log of all the numbers immediately reduces this to a classic 3-partition problem using addition, or equivalently, taking some number to the power of the numbers in any 3-partition addition problem turns it into a multiplication problem such as this. That implies this problem should not be any easier. We do have here the prime factorization, whereas that factorization would not be prime, but does that help us?

Graphically, the surface xyz = 0 would look like the union of the xy-, yz- and xz-planes, and for any positive n, the equation would look like y = n/xz, so each slice along a coordinate plane would be a hyperbola. We can generally say that the quantity we’re trying to minimize is lowest at the origin and grows most rapidly along the line where x = y = z. If we can search only along this manifold, we might be able to reduce to a two-dimensional problem.

$\endgroup$
  • $\begingroup$ If x+y+z=n, 2^n=2^(x+y+z)=2^x*2^y*2^z, which is an instance of this problem minus the restriction that the inputs are a prime decomposition of the product. They would instead all be powers of two. $\endgroup$ – Davislor Sep 28 '15 at 23:43
  • $\begingroup$ It’s true that the weight to minimize will be different, but if x=y=z in the original problem, won’t x'y'+x'z'+y'z' be minimized in the corresponding problem where each w is replaced by w'=2^w, meaning that if a solution to the original problem exists, the reduction would find it? We might get a spurious solution from the transformed problem, but we can detect that in linear time when converting back by verifying the sums. $\endgroup$ – Davislor Sep 29 '15 at 0:26
  • $\begingroup$ as above comment by GBach suggests, maximizing $xy + yz + xz$ subject to $xyz=n$ likely happens when $x,y,z$ are "close together" or have low deviation (from average). this is not necessarily the same as "close to $\sqrt[3]{n}$". the numerical examples given by Meyer on his page appear to fit this pattern. $\endgroup$ – vzn Sep 29 '15 at 4:08
  • $\begingroup$ @vzn: We’re trying to minimize surface area, not maximize it. If the 3-partition problem has a solution, that translates into a modified box-dimension problem where the solution is a perfect cube. A hypothetical poly-time algorithm would find the factors of the sides of that cube, and we could then translate it back into the original domain, while checking for spurious solutions, in linear time. That suggests an algorithm for a slightly-relaxed problem could serve as an oracle for a hard problem, making it unlikely a better-than-exponential algorithm exists. $\endgroup$ – Davislor Sep 29 '15 at 4:26
  • $\begingroup$ ? am not disagreeing with you. arent we saying the same thing? plz drop by Computer Science Chat to untangle/ sort this out further. also cant follow @D.W.s claim that the logarithmic transformation doesnt work, can you? am using some of your (seemingly on-target) analysis as basis for my own answer. $\endgroup$ – vzn Sep 29 '15 at 15:05

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.