Researching the Complexity of Boolean Functions with Computers
Kazuyuki Amano · Bulletin of the European Association for Theoretical Computer Science · 2010
With the rapid advances in computers, it becomes attractive to explore the use of computers to attack open problems in computational complexity. In this article, we concentrate on the problems of the complexity of Boolean functions, and overview several recent attempts to use computers in various ways to obtain concrete results on major problems in computational complexity. We discuss the problems on several computational models including ordered binary decision diagrams, Boolean circuits, and polynomial threshold representations of Boolean functions.