Random Boolean formulas representing any Boolean function with asymptotically equal probability

DOI10.1016/0012-365X(90)90223-5MaRDI QIDQ915747zbMATH OpenFDO

Authors Petr Savický

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexity of Boolean functionsrandom Boolean formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Boolean functions (06E30)

Recommendations

• scientific article; zbMATH DE number 4061157
• Asymptotic probability of values of random Boolean expressions
• Probabilities of Boolean functions given by random implicational formulas
• Formulas for approximating pseudo-Boolean random variables
• Stochastic Algorithms: Foundations and Applications
• scientific article; zbMATH DE number 3863117
• The Boolean functions computed by random Boolean formulas or how to grow the right function
• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
• On the approximation of a random Boolean function by the set of quadratic forms
• scientific article; zbMATH DE number 4209213

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 4095383 (Why is no real title available?)
• Short monotone formulae for the majority function

Cited in

(8)

• Uniform approximation of continuous functions by probability functions of the Boolean bases
• Formulas for approximating pseudo-Boolean random variables
• Complexity and Limiting Ratio of Boolean Functions over Implication
• Bent functions and random Boolean formulas
• Asymptotic probability of values of random Boolean expressions
• The fraction of large random trees representing a given Boolean function in implicational logic
• The Boolean functions computed by random Boolean formulas or how to grow the right function
• scientific article; zbMATH DE number 4209213 (Why is no real title available?)

This page was built for publication: Random Boolean formulas representing any Boolean function with asymptotically equal probability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q915747)