2-Xor Revisited: Satisfiability and Probabilities of Functions
Tóm tắt
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.
Tài liệu tham khảo
Andrews, G.E.: The theory of partitions. In: Encyclopedia of Mathematics and its Applications, vol. 2, Addison-Wesley Publishing Co., Reading (1976)
Banderier, C., Flajolet, P., Schaeffer, G., Soria, M.: Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Struct. Algorithms 19(3–4), 194–246 (2001)
Bender, E.A., Canfield, E.R., McKay, B.D.: The asymptotic number of labeled connected graphs with a given number of vertices and edges. Random Struct. Algorithms 1(2), 127–170 (1990)
Biggs, N.L., Lloyd, E.K., Wilson, R.J.: Graph Theory. Oxford University Press, Oxford (1974)
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)
Chauvin, B., Flajolet, P., Gardy, D., Gittenberger, B.: And/Or trees revisited. Comb. Probab. Comput. 13(4–5), 475–497 (2004)
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)
Comtet, L.: Advanced Combinatorics, enlarged edn. D. Reidel Publishing Co., Dordrecht (1974)
Creignou, N., Daudé, H.: Satisfiability threshold for random XOR-CNF formulas. Discrete Appl. Math. 96–97, 41–53 (1999)
Creignou, N., Daudé, H.: Smooth and sharp thresholds for random \(k\)-XOR-CNF satisfiability. Theor. Inform. Appl. 37(2), 127–147 (2003)
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)
Creignou, N., Daudé, H., Dubois, O.: Approximating the satisfiability threshold for random \(k\)-XOR-formulas. Comb. Probab. Comput. 12(2), 113–126 (2003)
Creignou, N., Daudé, H., Egly, U.: Phase transition for random quantified XOR-formulas. J. Artif. Intell. Res. 29, 1–18 (2007)
Daudé, H., Ravelomanana, V.: Random 2XorSat phase transition. Algorithmica 59(1), 48–65 (2011)
de Panafieu, E.: Analytic Combinatorics of Graphs, Hypergraphs and Inhomogeneous Graphs. PhD thesis, Université Paris-Diderot, Sorbonne Paris-Cité (2014)
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)
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
Drmota, M.: Random trees. Springer, Vienna (2009)
Erdős, P., Rényi, A.: On random graphs. Publ. Math. Debrecen 6, 290–297 (1959)
Flajolet, P., Knuth, D.E., Pittel, B.: The first cycles in an evolving graph. Discrete Math. 75(1–3), 167–215 (1989)
Flajolet, P., Salvy, B., Schaeffer, G.: Airy phenomena and analytic combinatorics of connected graphs. Electron. J. Comb. 11(1), R34 (30 pages) (2004)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
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(3), 317–349 (2012)
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)
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
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)
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)
Janson, S., Knuth, D., Łuczak, T., Pittel, B.: The birth of the giant component. Random Struct. Algorithms 4(3), 233–358 (1993)
Kozik, J.: Subcritical pattern languages for And/Or trees. In: Fifth Colloquium on Mathematics and Computer Science, Blaubeuren, Germany, September (2008). DMTCS Proceedings
Lefmann, H., Savický, P.: Some typical properties of large And/Or Boolean formulas. Random Struct. Algorithms 10, 337–351 (1997)
Pittel, B., Wormald, N.C.: Counting connected graphs inside-out. J. Comb. Theory Ser. B 93(2), 127–172 (2005)
Pittel, B., Yeum, J.-A.: How frequently is a system of 2-linear equations solvable? Electron. J. Comb. 17, R92 (50 pages) (2010)
van der Hofstad, R., Spencer, J.: Counting connected graphs asymptotically. Eur. J. Comb. 26(8), 1294–1320 (2006)
Woods, A.: On the probability of absolute truth for And/Or formulas. Bull. Symb. Logic 12(3), 523 (2005)
Wright, E.M.: The number of connected sparsely edged graphs. J. Graph Theory 1, 317–330 (1977)
Wright, E.M.: The number of connected sparsely edged graphs III: asymptotic results. J. Graph Theory 4(4), 393–407 (1980)
Zaionc, M.: On the asymptotic density of tautologies in logic of implication and negation. Rep. Math. Logic 39, 67–87 (2005)