Logical Approaches to Non-deterministic Polynomial Time over Semirings
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918151643463680 |
|---|---|
| author | Barlag, Timon Fröhlich, Nicolas Hankala, Teemu Hannula, Miika Hirvonen, Minna Holzapfel, Vivian Kontinen, Juha Meier, Arne Strieker, Laura |
| author_facet | Barlag, Timon Fröhlich, Nicolas Hankala, Teemu Hannula, Miika Hirvonen, Minna Holzapfel, Vivian Kontinen, Juha Meier, Arne Strieker, Laura |
| contents | We provide a logical characterization of non-deterministic polynomial time defined by BSS machines over semirings via existential second-order logic interpreted in the semiring semantics developed by Grädel and Tannen. Furthermore, we show that, similarly to the classical setting, the satisfiability problem of propositional logic in the semiring semantics is the canonical complete problem for this version of NP. Eventually, we prove that the true existential first-order theory of the semiring is a complete problem for the so-called Boolean part of this version of NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_26214 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Logical Approaches to Non-deterministic Polynomial Time over Semirings Barlag, Timon Fröhlich, Nicolas Hankala, Teemu Hannula, Miika Hirvonen, Minna Holzapfel, Vivian Kontinen, Juha Meier, Arne Strieker, Laura Logic in Computer Science We provide a logical characterization of non-deterministic polynomial time defined by BSS machines over semirings via existential second-order logic interpreted in the semiring semantics developed by Grädel and Tannen. Furthermore, we show that, similarly to the classical setting, the satisfiability problem of propositional logic in the semiring semantics is the canonical complete problem for this version of NP. Eventually, we prove that the true existential first-order theory of the semiring is a complete problem for the so-called Boolean part of this version of NP. |
| title | Logical Approaches to Non-deterministic Polynomial Time over Semirings |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2509.26214 |