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.