On the Number of Negations Needed to Compute Parity Functions

スポンサーリンク

概要

• 論文の詳細を見る

• We exactly determine the number of negations needed to compute the parity functions and the complement of the parity functions. We show that with k NOT gates, parity can be computed on at most 2^<k+1> - 1 variables, and parity complement on at most 2^<k+1> - 2 variables. The two bounds are shown to be tight.

• 一般社団法人電子情報通信学会の論文
• 1995-01-25

著者

• Nishino Tetsuro

  School Of Information Science Japan Advanced Institute Of Science And Technology

• Radhakrishnan Jaikumar

  Theoretical Computer Science Group Tata Institute Of Fundamental Research

関連論文

• On the Negation-Limited Circuit Complexity of Clique Functions
• The Emptiness Problem for Lexical-Functional Grammars is Undecidable
• A Simulation Result for Simultaneously Bounded AuxPDAs
• On the Number of Negations Needed to Compute Parity Functions

スポンサーリンク