The Library
AN EXTENSION OF KHRAPCHENKO THEOREM
Tools
UNSPECIFIED. (1991) AN EXTENSION OF KHRAPCHENKO THEOREM. INFORMATION PROCESSING LETTERS, 37 (4). pp. 215217. ISSN 00200190
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 parallelto c parallelto 1/2 = (SIGMAc(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 closedintegral (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:  00200190  
Official Date:  28 February 1991  
Dates: 


Volume:  37  
Number:  4  
Number of Pages:  3  
Page Range:  pp. 215217  
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 