The Complexity of Threshold Circuits for Parity Functions

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we show that a parity function with n variables can be computed by a threshold circuit of depth O((log n)/c) and size O((2^c log n)/c), for all 1≦c≦ ⌈log(n+1)⌉-1. From this construction, we obtain an O(log n/log log n) upper bound for the depth of polylogarithmic size threshold circuits for parity functions. By using the result of Impagliazzo, Paturi and Saks [5], we also show an Ω(log n/log log n) lower bound for the depth of the threshold circuits. This is an answer ot the open question posed in [11].

• 1997-01-25

著者

• Nishino Tetsuro

  Department Of Communications And Systems Engineering The University Of Electro-communications

• Sung S‐c

  School Of Information Science Japan Advanced Institute Of Science And Technology

• Sung Shao-chin

  School Of Information Science Japan Advanced Institute Of Science And Technology

• NISHINO Tetsuro

  Department of Communications and Systems Engineering, The University of Electro-Communications

関連論文

• Negation-limited circuit complexity of symmetric functions
• Lower bounds of the negation-limited circuit complexity
• The Complexity of Threshold Circuits for Parity Functions
• A Relationship between the Number of Negations and the Circuit Size
• An Introduction to Quantum Complexity Theory (第6回『非平衡系の統計物理』シンポジウム)

スポンサーリンク