Some typical properties of large AND/OR Boolean formulas

DOI<337::AID-RSA4>3.0.CO;2-X 10.1002/(SICI)1098-2418(199705)10:3<337::AID-RSA4>3.0.CO;2-XzbMath0874.60011OpenAlexW1966449461MaRDI QIDQ4344226

Petr Savický, Hanno Lefmann

Publication date: 2 November 1997

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199705)10:3<337::aid-rsa4>3.0.co;2-x

zbMATH Keywords

Boolean functionsize complexitybinary trees chosen from the uniform distribution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Boolean functions (06E30)

Related Items

The fraction of large random trees representing a given Boolean function in implicational logic ⋮ The distribution of height and diameter in random non-plane binary trees ⋮ A sprouting tree model for random boolean functions ⋮ Asymptotic Properties of Combinatory Logic ⋮ Intuitionistic vs. Classical Tautologies, Quantitative Comparison ⋮ What is the satisfiability threshold of random balanced Boolean expressions? ⋮ Fuzzy logics – quantitatively ⋮ Enumerating lambda terms by weighted length of their de Bruijn representation ⋮ Моменты весов случайных неравновероятных булевых функций ⋮ Tautologies over implication with negative literals ⋮ Complexity and Limiting Ratio of Boolean Functions over Implication ⋮ 2-Xor revisited: satisfiability and probabilities of functions ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability ⋮ Associative and commutative tree representations for Boolean functions