New answers tagged pr.probability
0
It's quite common for properties split numbers into "almost all" and "almost none" sets. For instance, almost none of Turing machines halt. Almost all real numbers are normal. Almost none of real number are algebraic.
19
They are separate (assuming $P \ne NP$). Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance of 3SAT. It's clear that testing whether $x$ satisfies $P$ is NP-hard, yet almost all strings satisfy it: the density $\to 1$ as $n \to \infty$.
Top 50 recent answers are included
