Satisfiability in many-valued sentential logic is NP-complete

DOI10.1016/0304-3975(87)90083-1zbMath0639.03042OpenAlexW2087171264MaRDI QIDQ1100196

Daniele Mundici

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90083-1

zbMATH Keywords

NP-completenessinfinite-valued calculus of Łukasiewiczmany-valued sentential logics

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Many-valued logic (03B50)

Related Items (40)

Logic of infinite quantum systems ⋮ Term satisfiability in \(\mathrm{FL}_{\mathrm{ew}}\)-algebras ⋮ Efficient representation of piecewise linear functions into Łukasiewicz logic modulo satisfiability ⋮ Constraint tableaux for two-dimensional fuzzy logics ⋮ Jan Łukasiewicz Life, Work, Legacy ⋮ Characterising equilibrium logic and nested logic programs: Reductions and complexity, ⋮ Turing complexity of Behncke-Leptin \(C^*\)-algebras with a two-point dual ⋮ Automated theorem proving by resolution in non-classical logics ⋮ Making fuzzy description logic more general ⋮ Equilibrium logic ⋮ Satisfiability checking in Łukasiewicz logic as finite constraint satisfaction ⋮ On finite-valued propositional logical calculi ⋮ European Summer Meeting of the Association for Symbolic Logic (Logic Colloquium '88), Padova, 1988 ⋮ On the relationship between fuzzy autoepistemic logic and fuzzy modal logics of belief ⋮ Many-valued logic and mixed integer programming ⋮ The Differential Semantics of Łukasiewicz Syntactic Consequence ⋮ Rational Pavelka logic: the best among three worlds? ⋮ On generalized hoops, homomorphic images of residuated lattices, and (G)BL-algebras ⋮ Complexity of some language fragments of fuzzy logics ⋮ Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics ⋮ Introduction ⋮ Complexity of fuzzy answer set programming under Łukasiewicz semantics ⋮ An efficient algorithm for representing piecewise linear functions into logic ⋮ Automated theorem proving for Łukasiewicz logics ⋮ Universal properties of Łukasiewicz consequence ⋮ The coherence of Łukasiewicz assessments is NP-complete ⋮ An asymptotically tight bound on countermodels for Łukasiewicz logic ⋮ Complexity of t-tautologies ⋮ MNiBLoS: a SMT-based solver for continuous t-norm based logics and some of their modal expansions ⋮ Effective Finite-Valued Approximations of General Propositional Logics ⋮ The consequence relation in the logic of commutative GBL-algebras is PSPACE-complete ⋮ Simple Bratteli diagrams with a Gödel-incomplete C*-equivalence problem ⋮ The complexity of McNaughton functions of one variable ⋮ Resolution and model building in the infinite-valued calculus of Łukasiewicz ⋮ New complexity results for Łukasiewicz logic ⋮ On the refutational completeness of signed binary resolution and hyperresolution ⋮ Lazy evaluations in Łukasiewicz type fuzzy logic ⋮ On the complexity of validity degrees in Łukasiewicz logic ⋮ Poset products as relational models ⋮ Complexity issues in Basic Logic

Cites Work

• Mapping Abelian \(\ell\)-groups with strong unit one-one into MV algebras
• Interpretation of AF \(C^*\)-algebras in Łukasiewicz sentential calculus
• Every Abelian \(\ell\)-group with two positive generators is ultrasimplicial
• Intuitionistic propositional logic is polynomial-space complete
• Deterministic propositional dynamic logic: finite models, complexity, and completeness
• Fragments of Many-Valued Statement Calculi
• The complexity of propositional linear temporal logics
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of theorem-proving procedures
• A theorem about infinite-valued sentential logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Satisfiability in many-valued sentential logic is NP-complete