On the Complexity of Validity Degrees in Łukasiewicz Logic

Autoři: RNDr. Zuzana Haniková, Ph.D.
Rok vydání: 2020
Typ publikace: Konferenční příspěvek (mezinárodní konf.)
Periodikum: Beyond the Horizon of Computability
Projekty: Usuzování se stupňovanými vlastnostmi
Bibliografická citace: HANIKOVÁ, Zuzana. On the Complexity of Validity Degrees in Łukasiewicz Logic. In: ANSELMO, M., DELLA VEDOVA, G., MANEA, F., PAULY, A., eds. Beyond the Horizon of Computability. Cham: Springer, 2020, S. 175-188. Lecture Notes in Computer Science, 12098. ISBN 978-3-030-51465-5. ISSN 0302-9743
Dostupné z: doi:10.1007/978-3-030-51466-2_15
DOI: 10.1007/978-3-030-51466-2_15
ID: 531136

Abstrakt

Lukasiewicz logic is an established formal system of manyvalued logic. Decision problems in both propositional and first-order case have been classified as to their computational complexity or degrees of undecidability. For the propositional fragment, theoremhood and provability from finite theories are coNP complete. This paper extends the range of results by looking at validity degree in propositional Lukasiewicz logic, a natural optimization problem to find the minimal value of a term under a finite theory in a fixed complete semantics interpreting the logic. A classification for this problem is provided using the oracle class FPNP, where it is shown complete under metric reductions.