Open AccessA Measure in Which Boolean Negation is Exponentially Powerful
Author(s) -
Sven Skyum
Publication year - 1982
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v11i154.7428
Subject(s) - negation , exponential growth , mathematics , measure (data warehouse) , boolean function , two element boolean algebra , discrete mathematics , algebra over a field , pure mathematics , computer science , data mining , mathematical analysis , programming language , filtered algebra
The power of negation in combinatorial complexity theory has for a long time been an intriguing question. In this paper we demonstrate that in the more restricted setting of projections among families of Boolean functions, negation can be exponentially powerful.