DS-1-2 On Formula Size Lower Bounds for Synthesis of Boolean Functions over Disjoint Sets of Variables

スポンサーリンク

概要

• 論文の詳細を見る

• Recently, it is shown that a complexity measure called sumPI which originates from quantum computing provides a good lower bound on the size of Boolean formulas. In this paper, we evaluate sumPI(f*g) in terms of sumPI(f) and sumPI(g), where f and g are "disjoint" Boolean functions, i.e., the sets of variables for f and g are disjoint, and * is an arbitrary Boolean operator. From this result, we obtain formula size lower bounds for any synthesis of disjoint Boolean functions. Moreover, we give a procedure that recursively generates Boolean formulas that cannot be simplified any more.

• 社団法人電子情報通信学会の論文
• 2007-03-07

著者

• FUKUHARA Hideaki

  Graduate School of Information Sciences, Tohoku University

• TAKIMOTO Eiji

  Department of Informatics, Kyushu University

• AMANO Kazuyuki

  Department of Computer Science, Gunma University

• Takimoto Eiji

  Graduate School Of Information Sciences Tohoku University

• Amano Kazuyuki

  Department Of Computer Science Gunma University

• Takimoto Eiji

  Kyushu Univ. Fukuoka‐shi Jpn

• Fukuhara Hideaki

  Graduate School Of Information Sciences Tohoku University

• Fukuhara Hideaki

  Tohoku Univ. Sendai‐shi Jpn

関連論文

• NPN-Representatives of a Set of Optimal Boolean Formulas
• Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators
• Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators
• NPN-Representatives of a Set of Optimal Boolean Formulas
• DS-1-2 On Formula Size Lower Bounds for Synthesis of Boolean Functions over Disjoint Sets of Variables
• An On-Line Prediction Algorithm Combining Several Prediction Strategies in the Shared Bet Model
• Online Allocation with Risk Information(Invited Papers from New Horizons in Computing)
• Relationships between Horn Formulas and XOR-MDNF Formulas(Foundations of Computer Science)
• On the Sample Complexity of Consistent Learning with One-Sided Error
• Proper learning algorithm for functions of $k$ terms under smooth distributions

スポンサーリンク