×

zbMATH — the first resource for mathematics

Satisfiability in many-valued sentential logic is NP-complete. (English) Zbl 0639.03042
Author’s summary: “Cook’s NP-completeness theorem is extended to all many-valued sentential logics, including the infinite-valued calculus of Łukasiewicz.”
Reviewer: M.Tetruašvili

MSC:
03D15 Complexity of computation (including implicit computational complexity)
03B50 Many-valued logic
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ben-Ari, M.; Halpern, J.Y.; Pnueli, A., Deterministic propositional dynamic logic: finite models, complexity, and completeness, J. comput. system sci., 25, 402-417, (1982) · Zbl 0512.03013
[2] Brøndsted, A., An introduction to convex polytopes, (1983), Springer New York · Zbl 0509.52001
[3] Cook, S.A., The complexity of theorem-proving procedures, Proc. 3rd ann. ACM symp. on theory of computing, 151-158, (1971)
[4] ()
[5] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco · Zbl 0411.68039
[6] Ladner, R.E., The computational complexity of provability in systems of modal propositional logic, SIAM J. comput., 6, 467-480, (1977) · Zbl 0373.02025
[7] McNaughton, R., A theorem about infinite-valued sentential logic, J. symbolic logic, 16, 1-13, (1951) · Zbl 0043.00901
[8] Mundici, D., Mapping abelian l-groups with strong unit one-one into MV algebras, J. algebra, 98, 76-81, (1986) · Zbl 0579.06016
[9] Mundici, D., Every abelian l-group with two positive generators is ultrasimplicial, J. algebra, 105, 236-241, (1987) · Zbl 0605.06014
[10] Mundici, D., Interpretation of AF C∗-algebras in łukasiewicz sentential calculus, J. funct. anal., 65, 15-63, (1986) · Zbl 0597.46059
[11] ()
[12] Rourke, C.P.; Sanderson, B.J., Introduction to piecewise-linear topology, (1972), Springer Berlin · Zbl 0254.57010
[13] Rose, A.; Rosser, J.B., Fragments of many-valued statement calculi, Trans. amer. math. soc., 87, 1-53, (1958) · Zbl 0085.24303
[14] Sistla, A.P.; Clarke, E.M., The complexity of propositional linear temporal logics, J. assoc. comput. Mach., 32, 733-749, (1985) · Zbl 0632.68034
[15] Statman, R., Intuitionistic propositional logic is polynomially space complete, Theoret. comput. sci., 9, 67-72, (1979) · Zbl 0411.03049
[16] Tarski, A.; Łukasiewicz, J., Investigations into the sentential calculus, (), 38-59
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.