The Boolean functions computed by random Boolean formulas or how to grow the right function

DOI10.1002/rsa.20095zbMath1083.94024arXivcs/0302028OpenAlexW2953147117MaRDI QIDQ5717773

Alex Brodsky, Nicholas J. Pippenger

Publication date: 10 January 2006

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

Full work available at URL: https://arxiv.org/abs/cs/0302028

zbMATH Keywords

growth processescomputational and structural complexityrandom Boolean functionsprobabilistic amplification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05)

Related Items (5)

The fraction of large random trees representing a given Boolean function in implicational logic ⋮ Enumerating lambda terms by weighted length of their de Bruijn representation ⋮ Complexity and Limiting Ratio of Boolean Functions over Implication ⋮ 2-Xor revisited: satisfiability and probabilities of functions ⋮ Associative and commutative tree representations for Boolean functions

This page was built for publication: The Boolean functions computed by random Boolean formulas or how to grow the right function