### Abstract

We consider the problem of characterizing sets of Boolean functions. Extending results of Ekin et al. and Pippenger, we show that a set of Boolean (or finite) functions can be characterized by a set of objects called 'generalized constraints' iff the set is closed under the operations of permutation of variables and addition of dummy variables. We show a relationship between sets of Boolean functions that are characterizable by a finite set of generalized constraints and sets of Boolean functions that have constant-size certificates of non-membership. We then explore whether certain particular sets of Boolean functions have constant-size certificates of non-membership; most notably, we show that the well-known set of Boolean threshold functions does not have constant-size certificates of non-membership. Finally, we extend results of Pippenger to develop a Galois theory for sets of Boolean functions closed under the operations of permutation of variables and addition of dummy variables.

Original language | English (US) |
---|---|

Pages (from-to) | 211-232 |

Number of pages | 22 |

Journal | Discrete Mathematics |

Volume | 226 |

Issue number | 1-3 |

DOIs | |

State | Published - 2001 |

### Keywords

- Boolean functions
- Certificates of non-membership
- Constraints
- Galois theory
- Minors

### ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'On generalized constraints and certificates'. Together they form a unique fingerprint.

## Cite this

*Discrete Mathematics*,

*226*(1-3), 211-232. https://doi.org/10.1016/S0012-365X(00)00166-7