A complexity theory based on Boolean algebra

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
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.
Original languageEnglish
JournalAssociation for Computing Machinery. Journal
Volume32
Issue2
Pages (from-to)484-502
Number of pages9
ISSN0004-5411
DOIs
Publication statusPublished - 1985

See relations at Aarhus University Citationformats

ID: 37215129