The Library
AN EXTENSION OF KHRAPCHENKO THEOREM
Tools
UNSPECIFIED (1991) AN EXTENSION OF KHRAPCHENKO THEOREM. INFORMATION PROCESSING LETTERS, 37 (4). pp. 215-217. ISSN 0020-0190.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
Khrapchenko's theorem is a classical result yielding lower bounds on the formula complexity of Boolean functions over the unate basis. In particular, it can yield a tight n2 lower bound on the formula complexity of the parity function.
In this note we consider an extended definition of formula size in which each variable may be assigned a different cost. We then generalize Khrapchenko's theorem to cover this new definition and in particular derive a parallel-to c parallel-to 1/2 = (SIGMA-c(i)1/2)2 lower bound on the generalized formula size complexity of the parity function of n variables with cost vector c = (c1,..., c(n)). This bound is shown to be tight to within a factor of 2 by methods similar to Huffman coding.
The extended definition of formula size arises naturally in cases where formulae for compound functions like closed-integral (g1,..., gn) are sought.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Journal or Publication Title: | INFORMATION PROCESSING LETTERS | ||||
Publisher: | ELSEVIER SCIENCE BV | ||||
ISSN: | 0020-0190 | ||||
Official Date: | 28 February 1991 | ||||
Dates: |
|
||||
Volume: | 37 | ||||
Number: | 4 | ||||
Number of Pages: | 3 | ||||
Page Range: | pp. 215-217 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |