Links between complexity theory and constrained block coding

Abstract

The goal of this paper is to establish links between computational complexity theory and the theory and practice of constrained block coding. The complexities of several fundamental problems in constrained block coding are shown to be complete in various classes of the existing complexity-theoretic structure. The results include (relatively rare) ∑2p-, ∑3p-, and NPPP-completeness results. Two types of problems are considered: (1) the problem of designing encoder and decoder circuits using minimum or approximately minimum hardware for a given constraint and a given rate; (2) computing the maximum rate of a block code for a given constraint and codeword length. In both cases, a constraint is specified by a deterministic finite state transition diagram. Another question studied is whether maximum-rate block codes can always be implemented by encoders and decoders of polynomial size. The answer to this question is shown to be closely related to the complexity of PP.