1 Deterministic and non-deterministic models of computation According to the Cobham-Edmonds Thesis the complexity class \(\textbf{P}\) describes the class of feasibily decidable problems. As we have just seen, this class is defined in terms of the reference model \(\mathfrak{T}\) in virtue of the assumption that it is a ‘reasonable’ model of computation. Several other models of computation are also studied in complexity theory not because they are presumed to be accurate representations of the c