Record Details

Number of restrictions of a Boolean function act as a complexity measure

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Number of restrictions of a Boolean function act as a complexity measure
 
Creator CHANDE, V
POONACHA, PG
 
Subject restrictions
boolean function
complexity measure
 
Description Complexity of boolean functions can be computed in many ways. Various complexity measures exist which are based on different models of representation of the boolean function. The complexity measures range from very coarse and simple to very fine and hard to compute. The introduced complexity meausre called Restriction complexity is a measure based on number of restrictions of a boolean function. In this paper we define restriction complexity, compute its values for some functions, and determine its range in the form of upper and lower bounds on it. We also show that restriction complexity is close to the cardinality of support measure in an almost all sense as defined by Abu-Mostafa.
 
Publisher INST ELECTRONICS TELECOMMUNICATION ENGINEERS
 
Date 2011-08-03T06:11:44Z
2011-12-26T12:54:04Z
2011-12-27T05:41:24Z
2011-08-03T06:11:44Z
2011-12-26T12:54:04Z
2011-12-27T05:41:24Z
1997
 
Type Article
 
Identifier IETE JOURNAL OF RESEARCH, 43(1), 3-10
0377-2063
http://dspace.library.iitb.ac.in/xmlui/handle/10054/8922
http://hdl.handle.net/10054/8922
 
Language en