×

zbMATH — the first resource for mathematics

2-Xor revisited: satisfiability and probabilities of functions. (English) Zbl 1352.68193
Summary: 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.

MSC:
68R05 Combinatorics in computer science
06E30 Boolean functions
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrews, G.E.: The theory of partitions. In: Encyclopedia of Mathematics and its Applications, vol. 2, Addison-Wesley Publishing Co., Reading (1976) · Zbl 0371.10001
[2] Banderier, C; Flajolet, P; Schaeffer, G; Soria, M, Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Random Struct. Algorithms, 19, 194-246, (2001) · Zbl 1016.68179
[3] Bender, EA; Canfield, ER; McKay, BD, The asymptotic number of labeled connected graphs with a given number of vertices and edges, Random Struct. Algorithms, 1, 127-170, (1990) · Zbl 0745.05022
[4] Biggs, N.L., Lloyd, E.K., Wilson, R.J.: Graph Theory. Oxford University Press, Oxford (1974)
[5] Brodsky, A; Pippenger, N, The Boolean functions computed by random Boolean formulas or how to grow the right function, Random Struct. Algorithms, 27, 490-519, (2005) · Zbl 1083.94024
[6] Chauvin, B; Flajolet, P; Gardy, D; Gittenberger, B, And/or trees revisited, Comb. Probab. Comput., 13, 475-497, (2004) · Zbl 1077.94526
[7] Chauvin, B., Gardy, D., Mailler, C.: The growing tree distribution for Boolean functions. In: 8th SIAM Workshop on Analytic and Combinatorics (ANALCO), pp. 45-56 (2011)
[8] Comtet, L.: Advanced Combinatorics, enlarged edn. D. Reidel Publishing Co., Dordrecht (1974) · Zbl 0283.05001
[9] Creignou, N; Daudé, H, Satisfiability threshold for random XOR-CNF formulas, Discrete Appl. Math., 96-97, 41-53, (1999) · Zbl 0941.68151
[10] Creignou, N; Daudé, H, Smooth and sharp thresholds for random \(k\)-XOR-CNF satisfiability, Theor. Inform. Appl., 37, 127-147, (2003) · Zbl 1058.68080
[11] Creignou, N., Daudé, H.: Coarse and sharp transitions for random generalized satisfiability problems. In: Drmota, M., Flajolet, P., Gardy, D., Gittenberger, B. (eds.) Mathematics and Computer Science III, Trends Mathematics, pp. 507-516. Birkhäuser, Basel (2004) · Zbl 1091.68058
[12] Creignou, N; Daudé, H; Dubois, O, Approximating the satisfiability threshold for random \(k\)-XOR-formulas, Comb. Probab. Comput., 12, 113-126, (2003) · Zbl 1034.68048
[13] Creignou, N; Daudé, H; Egly, U, Phase transition for random quantified XOR-formulas, J. Artif. Intell. Res., 29, 1-18, (2007) · Zbl 1182.68232
[14] Daudé, H; Ravelomanana, V, Random 2xorsat phase transition, Algorithmica, 59, 48-65, (2011) · Zbl 1206.68285
[15] de Panafieu, E.: Analytic Combinatorics of Graphs, Hypergraphs and Inhomogeneous Graphs. PhD thesis, Université Paris-Diderot, Sorbonne Paris-Cité (2014) · Zbl 1103.05040
[16] de Panafieu, E., Gardy, D., Gittenberger, B., Kuba, M.: Probabilities of 2-xor functions. In: Pardo, A., Viola, A. (eds.) International Conference LATIN, vol 8392. Springer Lecture Notes in Computer Science (2014) · Zbl 1351.68192
[17] de Panafieu, E., Ravelomanana, V.: Analytic description of the phase transition of inhomogeneous multigraphs. Eur. J. Comb. (2014). Accepted. Also available at http://arxiv.org/pdf/1409.8424.pdf · Zbl 1293.05355
[18] Drmota, M.: Random trees. Springer, Vienna (2009) · Zbl 1170.05022
[19] Erdős, P; Rényi, A, On random graphs, Publ. Math. Debrecen, 6, 290-297, (1959) · Zbl 0092.15705
[20] Flajolet, P; Knuth, DE; Pittel, B, The first cycles in an evolving graph, Discrete Math., 75, 167-215, (1989) · Zbl 0696.05045
[21] Flajolet, P., Salvy, B., Schaeffer, G.: Airy phenomena and analytic combinatorics of connected graphs. Electron. J. Comb. 11(1), R34 (30 pages) (2004) · Zbl 1053.05064
[22] Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) · Zbl 1165.05001
[23] Fournier, H; Gardy, D; Genitrini, A; Gittenberger, B, The fraction of large random trees representing a given Boolean function in implicational logic, Random Struct. Algorithms, 40, 317-349, (2012) · Zbl 1239.03004
[24] Fournier, H., Gardy, D., Genitrini, A., Zaionc, M.: Classical and intuitionistic logic are asymptotically identical. In: 16th Annual Conference on Computer Science Logic (EACSL), vol 4646 of Lecture Notes in Computer Science, pp. 177-193 (2007) · Zbl 1179.03015
[25] Genitrini, A., Gittenberger, B., Kraus, V., Mailler, C.: Associative and Commutative Tree Representations for Boolean Functions. (2011). Submitted. Also available at http://arxiv.org/abs/1305.0651 · Zbl 1314.94120
[26] Genitrini, A., Gittenberger, B., Kraus, V., Mailler, C.: Probabilities of Boolean functions given by random implicational formulas. Electron. J. Comb. 19(2), P37 (20 pages) (electronic) (2012) · Zbl 1243.03011
[27] Genitrini, A., Kozik, J., Zaionc, M.: Intuitionistic vs. classical tautologies, quantitative comparison. In: Types for Proofs and Programs, vol. 4941, pp. 100-109. Springer Lecture Notes in Computer Science (2008) · Zbl 1138.03309
[28] Janson, S; Knuth, D; Łuczak, T; Pittel, B, The birth of the giant component, Random Struct. Algorithms, 4, 233-358, (1993) · Zbl 0795.05127
[29] Kozik, J.: Subcritical pattern languages for And/Or trees. In: Fifth Colloquium on Mathematics and Computer Science, Blaubeuren, Germany, September (2008). DMTCS Proceedings · Zbl 1355.68162
[30] Lefmann, H; Savický, P, Some typical properties of large and/or Boolean formulas, Random Struct. Algorithms, 10, 337-351, (1997) · Zbl 0874.60011
[31] Pittel, B; Wormald, NC, Counting connected graphs inside-out, J. Comb. Theory Ser. B, 93, 127-172, (2005) · Zbl 1057.05044
[32] Pittel, B., Yeum, J.-A.: How frequently is a system of 2-linear equations solvable? Electron. J. Comb. 17, R92 (50 pages) (2010) · Zbl 1193.05147
[33] Hofstad, R; Spencer, J, Counting connected graphs asymptotically, Eur. J. Comb., 26, 1294-1320, (2006) · Zbl 1103.05040
[34] Woods, A, On the probability of absolute truth for and/or formulas, Bull. Symb. Logic, 12, 523, (2005)
[35] Wright, EM, The number of connected sparsely edged graphs, J. Graph Theory, 1, 317-330, (1977) · Zbl 0337.05119
[36] Wright, EM, The number of connected sparsely edged graphs III: asymptotic results, J. Graph Theory, 4, 393-407, (1980) · Zbl 0416.05048
[37] Zaionc, M, On the asymptotic density of tautologies in logic of implication and negation, Rep. Math. Logic, 39, 67-87, (2005) · Zbl 1098.03019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.