Descriptive complexity theory is concerned with devising logics that can express all problems decidable in a given complexity class. Examples are Fagin's result that Σ¹₁ captures NP, and Immerman and Vardi's result that LFP captures PTIME.

In this thesis, we discuss two logics that have been proposed in the literature (by Malmström and Khanna, respectively), and that only allow to express optimization problems that admit an FPTAS or PTAS, respectively. We present the previous results, and offer simplified proofs for several of them.