This article presents detailed complexity analysis of the encoding and decoding problems for the segmental phonology. The segmental model is a generative theory of phonological dependencies. As such, it poses two computational problems. The first computational problem is the problem of actually encoding the dependencies of a given phonology into a given representation of phonological knowledge (the encoding problem). The second computational problem is the problem of deciding whether a given phonological representation encodes the dependencies of a given phonology (the decoding problem). We begin by proving that the encoding and decoding problems are both undecidable in the segmental model. Next, we motivate a simplified segmental model, that more accurately models the phonological dependencies actually proposed in the phonological literature. The simplified segmental model is a more restricted and more natural reformalization of the segmental model. To conclude, we prove that the encoding and decoding problems are NP-complete in this simplified segmental model.