2-Xor revisited: satisfiability and probabilities of functions
Authors:
- Danièle GardyDGDanièle Gardy
- Bernhard GittenbergerBGBernhard Gittenberger
- Markus KubaMKMarkus Kuba
Preprint
Abstract
The problem 2-Xor-Sat asks for the probability that a random expression, built as a conjunction of clauses $x \oplus y$, is satisfiable. We revisit this classical problem by giving an alternative, explicit expression of this probability. We then consider a refinement of it, namely the probability that a random expression computes a specific Boolean function. The answers to both problems involve a description of 2-Xor expressions as multigraphs and use classical methods of analytic combinatorics by expressing probabilities through coefficients of generating functions.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- The fraction of large random trees representing a given Boolean function in implicational logicRandom Structures & Algorithms, 2011
- Counting connected graphs asymptoticallyEuropean Journal of Combinatorics, 2006
- The Boolean functions computed by random Boolean formulas or how to grow the right functionRandom Structures & Algorithms, 2005
- Random maps, coalescing saddles, singularity analysis, and Airy phenomenaRandom Structures & Algorithms, 2001
- Some typical properties of large AND/OR Boolean formulasRandom Structures & Algorithms, 1997
- The birth of the giant componentRandom Structures & Algorithms, 1993
- The asymptotic number of labeled connected graphs with a given number of vertices and edgesRandom Structures & Algorithms, 1990
- The first cycles in an evolving graphDiscrete Mathematics, 1989
- The number of connected sparsely edged graphs. III. Asymptotic resultsJournal of Graph Theory, 1980
- The number of connected sparsely edged graphsJournal of Graph Theory, 1977