2003/01/01 by Reiner Hähnle · 1 citation
Computer Science · Mathematics · #Advanced Algebra and Logic #Artificial intelligence #Computer science #Context (archaeology) #Description logic #Discrete mathematics #Intermediate logic #Logic, Reasoning, and Knowledge #Mathematics #Propositional calculus #Propositional variable #T-norm fuzzy logics #Theoretical computer science #semigroups and automata theory
paper · doi:10.1007/978-3-7908-1769-0_9
openalex publication_date 2003/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
As is the case for other logics, a number of complexity-related questions can be posed in the context of many-valued logic. Some of these, such as the complexity of the sets of satisfiable and valid formulas in various logics, are completely standard; others only make sense in a many-valued context. In this overview I concentrate on two kinds of complexity problems related to many-valued logic: first, I discuss the complexity of the membership problem in various languages, such as the satisfiable, respectively, the valid formulas in some well-known logics. Second, I discuss the size of representations of many-valued connectives and quantifiers, because this has a direct impact on the complexity of many kinds of deduction systems. I include results on both propositional and on first-order logic. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.