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
