A Class of Boolean Functions with Linear Combinatorial Complexity
In this paper we investigate the combinatorial complexity of Boolean functions satisfying a certain property, P^nk,m. A function of n variable has the P^nk,m property if there are at least m functions obtainable from each way of restricting it to a subset of n-l variables. We show that the complexit...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148883 |
| _version_ | 1811092380850323456 |
|---|---|
| author | Hsieh, W. N. Harper, L.H. Savage, J.E. |
| author_facet | Hsieh, W. N. Harper, L.H. Savage, J.E. |
| author_sort | Hsieh, W. N. |
| collection | MIT |
| description | In this paper we investigate the combinatorial complexity of Boolean functions satisfying a certain property, P^nk,m. A function of n variable has the P^nk,m property if there are at least m functions obtainable from each way of restricting it to a subset of n-l variables. We show that the complexity of P^n3,5 function is no less than 7n-4/6, and this bound cannot be much improved. Further, we find that for each k, there are p^k,2^k functions with complexity linear in n. |
| first_indexed | 2024-09-23T15:17:15Z |
| id | mit-1721.1/148883 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:17:15Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1488832023-04-07T15:16:44Z A Class of Boolean Functions with Linear Combinatorial Complexity Hsieh, W. N. Harper, L.H. Savage, J.E. In this paper we investigate the combinatorial complexity of Boolean functions satisfying a certain property, P^nk,m. A function of n variable has the P^nk,m property if there are at least m functions obtainable from each way of restricting it to a subset of n-l variables. We show that the complexity of P^n3,5 function is no less than 7n-4/6, and this bound cannot be much improved. Further, we find that for each k, there are p^k,2^k functions with complexity linear in n. 2023-03-29T14:04:47Z 2023-03-29T14:04:47Z 1974-10 https://hdl.handle.net/1721.1/148883 MIT-LCS-TM-055 MAC-TM-055 application/pdf |
| spellingShingle | Hsieh, W. N. Harper, L.H. Savage, J.E. A Class of Boolean Functions with Linear Combinatorial Complexity |
| title | A Class of Boolean Functions with Linear Combinatorial Complexity |
| title_full | A Class of Boolean Functions with Linear Combinatorial Complexity |
| title_fullStr | A Class of Boolean Functions with Linear Combinatorial Complexity |
| title_full_unstemmed | A Class of Boolean Functions with Linear Combinatorial Complexity |
| title_short | A Class of Boolean Functions with Linear Combinatorial Complexity |
| title_sort | class of boolean functions with linear combinatorial complexity |
| url | https://hdl.handle.net/1721.1/148883 |
| work_keys_str_mv | AT hsiehwn aclassofbooleanfunctionswithlinearcombinatorialcomplexity AT harperlh aclassofbooleanfunctionswithlinearcombinatorialcomplexity AT savageje aclassofbooleanfunctionswithlinearcombinatorialcomplexity AT hsiehwn classofbooleanfunctionswithlinearcombinatorialcomplexity AT harperlh classofbooleanfunctionswithlinearcombinatorialcomplexity AT savageje classofbooleanfunctionswithlinearcombinatorialcomplexity |