Tag Info

13

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 the running time by at most a polynomial factor (the exact factor depending on the model of computation), and so the new machine is also in ZPP. The new machine ...

9

I'm not sure this is a statement about primes so much as it is a statement about secret key generation: if the method is deterministic (e.g. take the smallest prime larger than 10^20), then your adversary can simply reproduce the computation to find your secret key.

9

If you have a coin which has an uncomputable probability of landing heads, then you can estimate with bounded error the first $k$ bits of this probability using $O(4^{k})$ coin flips. This lets you construct a machine with bounded error that computes an uncomputable function. The uncomputable function is the $k$th bit of the probability. The computation is ...

6

To exactly sample from the binomial distribution on $\{0,1,\cdots,n\}$ requires $n$ random bits. However, we can approximately sample with $O(\log(n/\varepsilon))$ bits, where $\varepsilon$ is the statistical distance from binomial we allow. Let $$a_0=0, ~~~~a_{k+1}=a_k+{n \choose k} \cdot 2^{-n} ~~~~(k \in \{0,1,\cdots,n\}).$$ We can sample exactly from ...

6

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 over the set of all solutions, here is an algorithm to sample from all solutions: Count the number of solutions; call it $N_0$. (As you say, this can be done ...

4

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: \begin{align*} \Pr[e4] &\gt 0.25 & \text{prob of correct guess} \\ \Pr[e2] + \Pr[e4] &\leq 0.5 & \text{prob guess a correctly} \\ \Pr[e3] + \Pr[e4] &\leq 0.5 & \...

3

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 well not result as well. So the proof goes that way: first let's define this array: b\a | 0 || 1 | _____________________ 0 | c | d || g | h | | ...

2

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 contexts in which satisfaction is not Boolean. Examples of this include probabilistic reasoning (captured by PSL that you mentioned), fuzzy logic, quantitative ...

2

I hope the following partially answers your question. I've never seen this observation published anywhere (please correct me if I'm wrong). First of all, FQMA - a quantum analog of FNP - was defined: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fqma One of the compelling reasons to define the complexity class NP is that there is a decision to ...

2

Using the alias method you can make do with $\lceil \log_2 (k+1) \rceil + 2$ bits on average. In preprocessing you prepare a table of length $k+1$ in which each cell is partitioned into two parts by some threshold $\theta_i \in [0,1]$, and the "lower" and "upper" parts are labelled by outcomes. To sample, you first choose a uniformly random cell $i$, and ...

1

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) \notin L_A.$$ Here as I understand it $L_A$ is the language accepted by $A$, $\langle A\rangle$ is a code for $A$, and $D$ takes such a code and outputs a string ...

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