Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2404.17784 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916229356191744 |
|---|---|
| author | Badia, Guillermo Droste, Manfred Noguera, Carles Paul, Erik |
| author_facet | Badia, Guillermo Droste, Manfred Noguera, Carles Paul, Erik |
| contents | Fagin's seminal result characterizing $\mathsf{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 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 $\mathsf{NP}[\mathcal{S}], \mathsf{FP}[\mathcal{S}]$, $\mathsf{FPLOG}[\mathcal{S}]$, $\mathsf{FPSPACE}[\mathcal{S}]$, and $\mathsf{FPSPACE}_{poly}[\mathcal{S}]$ in terms of definability in suitable weighted logics for an arbitrary semiring $\mathcal{S}$. In particular, we 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 $\mathsf{P}$) and the Abiteboul--Vianu--Vardi's theorem (originally for $\mathsf{PSPACE}$). We also address a recent open problem proposed by Eiter and Kiesel. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17784 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Logical Characterizations of Weighted Complexity Classes Badia, Guillermo Droste, Manfred Noguera, Carles Paul, Erik Logic Fagin's seminal result characterizing $\mathsf{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 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 $\mathsf{NP}[\mathcal{S}], \mathsf{FP}[\mathcal{S}]$, $\mathsf{FPLOG}[\mathcal{S}]$, $\mathsf{FPSPACE}[\mathcal{S}]$, and $\mathsf{FPSPACE}_{poly}[\mathcal{S}]$ in terms of definability in suitable weighted logics for an arbitrary semiring $\mathcal{S}$. In particular, we 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 $\mathsf{P}$) and the Abiteboul--Vianu--Vardi's theorem (originally for $\mathsf{PSPACE}$). We also address a recent open problem proposed by Eiter and Kiesel. |
| title | Logical Characterizations of Weighted Complexity Classes |
| topic | Logic |
| url | https://arxiv.org/abs/2404.17784 |