A complexity theory based on Boolean algebra

Sven Skyum; Leslie Valiant

doi:10.1145/3149.3158

A complexity theory based on Boolean algebra

Sven Skyum, Leslie Valiant

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

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.

Original language	English
Journal	Association for Computing Machinery. Journal
Volume	32
Issue	2
Pages (from-to)	484-502
Number of pages	9
ISSN	0004-5411
DOIs	https://doi.org/10.1145/3149.3158
Publication status	Published - 1985

Access to Document

10.1145/3149.3158

Cite this

@article{cb85e7a1601246ae82a402d5b764d093,

title = "A complexity theory based on Boolean algebra",

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.",

author = "Sven Skyum and Leslie Valiant",

year = "1985",

doi = "10.1145/3149.3158",

language = "English",

volume = "32",

pages = "484--502",

journal = "Association for Computing Machinery. Journal",

issn = "0004-5411",

publisher = "Association for Computing Machinery",

number = "2",

}

TY - JOUR

T1 - A complexity theory based on Boolean algebra

AU - Skyum, Sven

AU - Valiant, Leslie

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

U2 - 10.1145/3149.3158

DO - 10.1145/3149.3158

M3 - Journal article

SN - 0004-5411

VL - 32

SP - 484

EP - 502

JO - Association for Computing Machinery. Journal

JF - Association for Computing Machinery. Journal

IS - 2

ER -

A complexity theory based on Boolean algebra

Abstract

Access to Document

Fingerprint

Cite this