We investigate the computational complexity of various satisfiability problems in Łukasiewicz logic, restricting attention to valuations in the standard MV-algebra [0,1]. Specifically, we focus on maximal r -satisfiability – the task of maximizing the number of formulas whose valuation is at least a given rational r ∈ (0, 1]. We also consider the decisional and weighted versions of this problem, as well as the partial (weighted) r -satisfiability problem.
Computational complexity of some MaxSAT problems in Łukasiewicz logic
Lapenta S.
;Napolitano S.
2026
Abstract
We investigate the computational complexity of various satisfiability problems in Łukasiewicz logic, restricting attention to valuations in the standard MV-algebra [0,1]. Specifically, we focus on maximal r -satisfiability – the task of maximizing the number of formulas whose valuation is at least a given rational r ∈ (0, 1]. We also consider the decisional and weighted versions of this problem, as well as the partial (weighted) r -satisfiability problem.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
