For any positive $p,q\in\mathbb{N}$ there is a finite subset $S$ of $\{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $\sum_{s\in S} s=\frac{p}{q}$, see this article by Paul Erdös and Sherman Stein (Sums of distinct unit fractions. Proceedings of the American Mathematical Society, 14(1), 126131, 1963.) . Let $m(p,q)$ denote the minimal cardinality of such a subset $S$. Is there a polynomialtime algorithm to determine $m(p,q)$?

$\begingroup$ Distantly related: mathoverflow.net/questions/33628/… $\endgroup$ – Gerry Myerson Jan 2 '15 at 14:51
In fact, this is listed as an open problem in the Wikipedia page on Egyptian Fractions, presumably because they do use the output size as a parameter.
No such polynomialtime algorithm exists because in some instances it would take too long to write down (or store in memory) the answer. In particular, if $n$ is a positive integer, then we have $\sum_{k=1}^{m(n,1)} \frac{1}{k} \geq n$, which implies that $m(n,1) \geq \frac{1}{5} e^{n}$. In such an instance, the number of input bits is about $\log_{2}(n)$ and the number of output bits is around $n$.

$\begingroup$ What about polynomial in the size of the output? $\endgroup$ – Igor Rivin Jan 2 '15 at 18:18

$\begingroup$ The question is still quite subtle for fractions between 0 and 1. In this case, $m(p,q)$ is quite small ($O(\sqrt{\log(q)})$), but determining the precise value is probably quite hard (as hard as factoring in some cases probably). $\endgroup$ – Jeremy Rouse Jan 2 '15 at 20:09