The 2024 Developer Survey results are live! See the results

Tag Info

Hot answers tagged probabilistic-computation

Accepted

Power of randomness vs. power of indefinite computation

Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects ...
• 14.5k
Accepted

What are the consequences of $BPP \neq P$?

To me, the intuitive reason for believing that $BPP = P$ is that if you describe to me a randomized algorithm, then in practice, I can implement it by using a pseudorandom number generator (PRNG) ...
• 7,560
Accepted

Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

There is no such problem. If it's hard to sample, it's hard to integrate. Here is a sketch of the reason why. Represent every solution $x$ by a $n$-bit string $x_1,\dots,x_n$. If you can integrate ...
• 12.3k
Accepted

If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

There are 4 possibilities, name them e1-e4: e1 neither match e2 a only matches e3 b only matches e4 both match Now I restate what you want to prove: Suppose: ...
• 7,728

If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

So I found a simple proof, but the proof is a bit fastidious to write (the symmetries make it easy to check however). If you have a more elegant/fundamental way to prove it, let me know! Or if it's a ...
• 173
Accepted

Soft Truth Values in the PSL model

The question is quite broad, so my answer will also probably be broad. Traditional logic is Boolean, in the sense that every sentence evaluates to either true or false. However, there are many ...
• 5,596
Accepted

Probabilistic Turing machine of possibly correlated choices

Suppose that $D$ always yields the same value, with probability 1: namely, the value of Chaitin's constant. Then such a machine is basically equivalent to a Turing machine with oracle access to ...
• 12.3k
1 vote

What are the consequences of $BPP \neq P$?

I think, the main reason for most researchers to prefer the $BPP=P$ conjecture over $BPP\neq P$ is that there is a very strong asymmetry in their perceived difficulty. Specifically, (1) $BPP\neq P$ ...
• 11.4k
1 vote

Can we efficiently distinguish between P and BPP?

You defined that algorithm $D$ distinguishes $BPP$ from $P$ if there exists a language $L \in BPP$ such that for all $A \in PTM$, D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \...
• 4,485

Only top scored, non community-wiki answers of a minimum length are eligible