pith. sign in

arxiv: 1511.07813 · v1 · pith:IBK3L334new · submitted 2015-11-24 · 🧮 math.CO · math.PR

2-Xor revisited: satisfiability and probabilities of functions

classification 🧮 math.CO math.PR
keywords expressionprobabilityclassicalfunctionsprobabilitiesproblemrandomalternative
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.