The complexity of strict minimum message length inference

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 indeed for any SMML problem that is essentially one-dimensional in character. The problem in general is shown to be 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.