NPN-Representatives of a Set of Optimal Boolean Formulas

Hideaki FUKUHARA  Eiji TAKIMOTO  Kazuyuki AMANO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.6   pp.1008-1015
Publication Date: 2010/06/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Circuit Complexity
Keyword: 
formula complexity,  quantum adversary methods,  NPN-equivalence classes,  

Full Text: PDF(2.1MB)
>>Buy this Article


Summary: 
For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class CB of read-once Boolean formulas over the basis B that has the following property: For any F in CB, F can be transformed to an optimal formula (i.e., a simplest formula over the standard basis {AND, OR, NOT}) by replacing each occurrence of a basis function hB in F with an optimal formula for h. For a particular set of basis functions B* = {AND,OR,NOT,XOR,MUX}, we give a canonical form representation for CB* so that the set of canonical form formulas consists of only NPN-representatives in CB*.