Open AccessA Measure in Which Boolean Negation is Exponentially Powerful
Author(s) -
Sven Skyum
Publication year - 1982
Publication title -
daimi report series
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom