Strict Minimum Message Length (SMML) inference is an information-theoretic criterion for inductive inference introduced by Wallace and Boulton and is known to possess several desirable statistical properties. In this paper we examine its computational complexity. We give an efficient algorithm for the binomial case and show that the problem in general is NP-hard. A heuristic is discussed which gives good results for binomial and trinomial SMML inference. The complexity of the trinomial case remains open and is worth further investigation.