Logical Characterizations of Weighted Complexity Classes

ABSTRACT

Fagin’s seminal result characterizing NP 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 work, 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 NP[S], FP[S], FPLOG[S], FPSPACE[S], and FPSPACEpoly [S] in terms of definability in suitable weighted logics for an arbitrary semiring S, and present weighted versions of Fagin’s Theorem, (even for arbitrary structures, not necessarily ordered, the Immerman–Vardi Theorem, and the Abiteboul–Vianu–Vardi Theorem. Furthermore, we discuss applications to classical counting complexity classes, other complexity classes such as NPMV, ⊕P, MaxP[O(log n)] and MinP[O(log n)], respectively.

SHORT BIO:

Guillermo Badia is a Lecturer in Logic (continuing position) in the School of Historical and Philosophical Inquiry at the University of Queensland, Australia. From 2022-2025, his research is supported by an Australian Research Council Discovery Early Career Researcher Award (DE220100544). He serves as an editor of Archive for Mathematical  Logic and Journal of Multiple-Valued Logic and Soft Computing. According to the Mathematics Genealogy Project, he is one of the many academic descendants of G. H. Hardy through the path  G. H. Hardy – R. Rado – K. Gravett – John N. Crossley – John L. Bell – G. Priest – Z. Weber – G. Badia. His research interests include: Mathematical Fuzzy Logic and particularly model theory of many-valued predicate logics. Intuitionistic and bi-intuitionistic logic. Equality-free first-order logic. Second-order logic. Relevant and paraconsistent logic. Modal logic.