# 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

**Full text not available from this repository.**

## 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 |

Volume: | 37 |

Number: | 4 |

Number of Pages: | 3 |

Page Range: | pp. 215-217 |

Publication Status: | Published |

URI: | http://wrap.warwick.ac.uk/id/eprint/22820 |

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

### Actions (login required)

View Item |