Satisfiability problems for propositional calculi

descriptionPublicationkeyboard_double_arrow_right Article 01 Dec 1979 English Publisher:Springer Science and Business Media LLCJournal:Mathematical Systems Theory, volume 13, pages 45-53 (issn: 0025-5661, eissn: 1433-0490,

Copyright policy )

Authors: Harry R. Lewis;

doi: 10.1007/bf01744287

Satisfiability problems for propositional calculi

- Summary
- Subjects
- Metrics

Abstract

For each fixed set of Boolean connectives, how hard is it to determine satisfiability for formulas with only those connectives? We show that a condition sufficient for NP-completeness is that the functionx Λ ~ y be representable, and that any set of connectives not capable of representing this function has a polynomial-time satisfiability problem.

Related Organizations

Harvard University
United States

Keywords

polynomial-time satisfiability problem, Complexity of computation (including implicit computational complexity), Classical propositional logic, satisfiability for formulas, Boolean connectives, NP-completeness

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	36
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average