Descriptive complexity and weighted Turing machines

Fagin’s seminal result characterizing 𝖭𝖯 in terms of existential second-order logic started the fruitful field of descriptive complexity theory. In recent years, there has been much interest in the investigation of quantitative (weighted) models of computations. In this paper, we start the study of descriptive complexity based on weighted Turing machines over arbitrary semirings. We provide machine-independent characterizations (over ordered structures) of the weighted complexity classes 𝖭𝖯[],𝖫[],𝖥𝖯[], 𝖥𝖯𝖫𝖮𝖦[], 𝖥𝖯𝖲𝖯𝖠𝖢𝖤[], and 𝖥𝖯𝖲𝖯𝖠𝖢𝖤𝑝𝑜𝑙𝑦[] in terms of definability in suitable weighted logics for an arbitrary semiring . In particular, we state and prove weighted versions of Fagin’s theorem (even for arbitrary structures, not necessarily ordered, provided that the semiring is idempotent and commutative), the Immerman–Vardi’s theorem (originally for 𝖯) and the Abiteboul–Vianu–Vardi’s theorem (originally for 𝖯𝖲𝖯𝖠𝖢𝖤). We also discuss a recent open problem proposed by Eiter and Kiesel. Recently, the above mentioned weighted complexity classes have been investigated in connection to classical counting complexity classes. Furthermore, several classical counting complexity classes have been characterized in terms of particular weighted logics over the semiring ℕ of natural numbers. In this work, we cover several of these classes and obtain new results for others such as 𝖭𝖯𝖬𝖵, ⊕𝖯, or the collection of real-valued languages realized by nondeterministic polynomialtime real-valued Turing machines. Furthermore, our results apply to classes based on many other important semirings, such as the max-plus and the min-plus semirings over the natural numbers which correspond to the classical classes 𝖬𝖺𝗑𝖯[𝑂(log𝑛)] and 𝖬𝗂𝗇𝖯[𝑂(log𝑛)], respectively.