Evaluation of propositional formulas from the viewpoint of computational complexity

Bulletin of the Section of Logic 17 (2):62-66 (1988)
  Copy   BIBTEX

Abstract

Considering a fixed language of propositional calculus and the class of formulas with n propositional indeterminates, the evaluation of these formulas with respect to a given truth-values assignment for these indeterminates and with respect to the usual worst-case analysis is proved to belong to the O-class

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,164

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On meta complexity of propositional formulas and propositional proofs.Pavel Naumov - 2008 - Archive for Mathematical Logic 47 (1):35-52.
Coherence and Computational Complexity of Quantifier-free Dependence Logic Formulas.Jarmo Kontinen - 2013 - Studia Logica 101 (2):267-291.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Complexity Results for Modal Dependence Logic.Peter Lohmann & Heribert Vollmer - 2013 - Studia Logica 101 (2):343-366.
On Algorithmic Properties of Propositional Inconsistency-Adaptive Logics.Sergei P. Odintsov & Stanislav O. Speranski - 2012 - Logic and Logical Philosophy 21 (3):209-228.
Quantified propositional calculus and a second-order theory for NC1.Stephen Cook & Tsuyoshi Morioka - 2005 - Archive for Mathematical Logic 44 (6):711-749.
A modal perspective on the computational complexity of attribute value grammar.Patrick Blackburn & Edith Spaan - 1993 - Journal of Logic, Language and Information 2 (2):129-169.
Complexity and postmodernism: understanding complex systems.Paul Cilliers - 1998 - New York: Routledge.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Computation models for parameterized complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
Provability, complexity, grammars.Lev Dmitrievich Beklemishev - 1999 - Providence, RI: American Mathematical Society. Edited by Mati Reĭnovich Pentus & Nikolai Konstantinovich Vereshchagin.
Examining fragments of the quantified propositional calculus.Steven Perron - 2008 - Journal of Symbolic Logic 73 (3):1051-1080.

Analytics

Added to PP
2014-01-24

Downloads
10 (#1,118,334)

6 months
2 (#1,114,623)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references