On the Complexity of Validity Degrees in Łukasiewicz Logic

0531136 - ÚI 2021 RIV CH eng C - Conference Paper (international conference)
Haniková, Zuzana
On the Complexity of Validity Degrees in Łukasiewicz Logic.
Beyond the Horizon of Computability. Cham: Springer, 2020 - (Anselmo, M.; Della Vedova, G.; Manea, F.; Pauly, A.), s. 175-188. Lecture Notes in Computer Science, 12098. ISBN 978-3-030-51465-5. ISSN 0302-9743.
[CiE 2020: Conference on Computability in Europe /16./. Salerno (IT), 29.06.2020-03.07.2020]
R&D Projects: GA ČR(CZ) GA18-00113S
Institutional support: RVO:67985807
Keywords : Łukasiewicz logic * propositional constants * validity degree * computational complexity * Rational Pavelka Logic
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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.
Permanent Link: http://hdl.handle.net/11104/0309862