Algorithm to minimize surface area, given volume 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.
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:


Given n, find the cube root.    
Set an initial value integer s1 at the ceiling of that cube root.    
Test to see if s1 is a divisor of n, and if not, reduce s1 by 1.    
If a divisor s1 is found, set an initial s2 to be the ceiling of the square root of (n/s1).    
Then test to see if s2 is a divisor of n/s1, and if not, reduce s2 by 1.    
When a divisor s2 is found, s3 then is set to n/(s1*s2).
The current surface area is calculated by 2*(s1*s2 + s1*s3 + s2*s3).
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&gt;=1:
        while n % s1 &gt; 0:  
            s1 = s1 - 1
        s1quot = int(n/s1) 
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2&gt;=1:
            while s1quot % s2 &gt; 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&lt;minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1    
    return minSA