On the number of negations needed to compute parity functions

Nishino, Tetsuro ; Radhakrishnan, Jaikumar (1995) On the number of negations needed to compute parity functions IEICE - Transactions on Info and Systems, E78-D (1). pp. 90-91. ISSN 0916-8532

Full text not available from this repository.

Official URL: http://search.ieice.org/bin/summary.php?id=e78-d_1...

Abstract

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 2k+1-1 variables, and parity complement on at most 2k+1-2 variables. The two bounds are shown to be tight.

Item Type:Article
Source:Copyright of this article belongs to Oxford University Press.
Keywords:Computational Complexity; Boolean Circuit; Parity Function
ID Code:89526
Deposited On:27 Apr 2012 14:17
Last Modified:27 Apr 2012 14:17

Repository Staff Only: item control page