
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

NPNRepresentatives 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.E93A
No.6
pp.10081015 Publication Date: 2010/06/01
Online ISSN: 17451337 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Circuit Complexity Keyword: formula complexity, quantum adversary methods, NPNequivalence 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 C_{B} of readonce Boolean formulas over the basis B that has the following property: For any _{F} in C_{B}, 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 h ∈ B 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 C_{B*} so that the set of canonical form formulas consists of only NPNrepresentatives in C_{B*}.

