Authors
Serafina Lapenta
Sebastiano Napolitano
Date (dd-mm-yyyy)
2026-03-15
Title
Computational complexity of some MaxSAT problems in Łukasiewicz logic
Journal
Fuzzy Sets and Systems
Volume
527
Publication Year
2026-03-15
Document type
Article
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.

URL
go to publisher's site
Permalink
https://hdl.handle.net/11245.1/1339b376-c832-401f-991b-31e8a224b494