Publication:3575996
From MaRDI portal
zbMath1193.03016MaRDI QIDQ3575996
Publication date: 28 July 2010
Full work available at URL: https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAF0101/0.html
complexity; Boolean function; probability distribution for Boolean functions; probability of tautologies
68Q25: Analysis of algorithms and problem complexity
03B05: Classical propositional logic
06E30: Boolean functions
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Unnamed Item, On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations, Simplifications of Uniform Expressions Specified by Systems, In the full propositional logic, 5/8 of classical tautologies are intuitionistically valid, Asymptotic densities in logic and type theory, Analysis of an efficient reduction algorithm for random regular expressions based on universality detection, Associative and commutative tree representations for Boolean functions, The fraction of large random trees representing a given Boolean function in implicational logic, Asymptotic Properties of Combinatory Logic, Intuitionistic vs. Classical Tautologies, Quantitative Comparison, Complexity and Limiting Ratio of Boolean Functions over Implication