Advances in molecular biology may mean that almost any protein sequence can be synthesised, but perhaps this has served to highlight the inadequacy of theoretical work. For a given protein fold, it is probably not possible to reliably predict an ideal sequence. We identify and survey several aspects of the problem. Firstly, it is not clear what is the best way to score a sequence-structure pair. Secondly, there is no consensus as to what the score function should represent (free energy or some abstract measure of sequence-structure compatibility). Finally, the number of possible sequences is astronomical and searching this space poses a daunting optimisation problem. These problems are discussed in the light of recent experimental successes.