The shortest disjunctive normal form of a random Boolean function

DOI10.1002/rsa.10065zbMath1023.94023OpenAlexW2139991023MaRDI QIDQ4800394

Nicholas J. Pippenger

Publication date: 3 April 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10065

zbMATH Keywords

disjunctive normal formaverage lengthrandom Boolean function

Mathematics Subject Classification ID

Boolean functions (06E30)

Related Items (3)

Approximating Boolean Functions with Depth-2 Circuits ⋮ Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms ⋮ On the Minimization of Boolean Functions for Additive Complexity Measures

Cites Work

• On a packing and covering problem
• Near perfect coverings in graphs and hypergraphs
• Unnamed Item

This page was built for publication: The shortest disjunctive normal form of a random Boolean function