A complexity theory based on Boolean algebra
- 1 April 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (2) , 484-502
- https://doi.org/10.1145/3149.3158
Abstract
A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are considered. It is shown that much of what is of everyday relevance in Turing-machine-based complexity theory can be replicated easily and naturally in this elementary framework. Finer distinctions about the computational relationships among natural problems can be made than in previous formulations and some negative results are proved.Keywords
This publication has 6 references indexed in Scilit:
- Fast parallel computation of polynomials using few processorsPublished by Springer Nature ,1981
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977
- Complete problems for deterministic polynomial timeTheoretical Computer Science, 1976
- The Hardest Context-Free LanguageSIAM Journal on Computing, 1973
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970