Computational complexity of some MaxSAT problems in Łukasiewicz logic
Serafina Lapenta, Sebastiano Napolitano · Fuzzy Sets and Systems · 2025
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.