Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with probability:
TR97-057 | 3rd November 1997
Petr Savicky

Complexity and Probability of some Boolean Formulas

For any Boolean function $f$ let $L(f)$ be its formula size
complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and
every $k\le n/2$, we describe a probabilistic distribution
on formulas in the basis $\{\land,\oplus,1\}$ in some given set of
$n$ variables and of the ... more >>>

TR16-154 | 21st September 2016
Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor

Logical Induction

We present a computable algorithm that assigns probabilities to every logical statement in a given formal language, and refines those probabilities over time. For instance, if the language is Peano arithmetic, it assigns probabilities to all arithmetical statements, including claims about the twin prime conjecture, the outputs of long-running ... more >>>

ISSN 1433-8092 | Imprint