If E does not have i.o.-$2^{o(n)}$ circuits, then P=BPP, but this does not tell us about the fine-grained containments between $\mathrm{Time}(n^a)$ and $\mathrm{BPTime}(n^b)$.

Are there reasonable computational complexity conjectures that imply a fine-grained relationship between levels of P and BPP?  Same question for approximation problems, including CAPP (approximate probability that a given circuit will accept random input).

Also, if for every $ε>0$, $\mathrm{Time}(O(2^n))$ does not have i.o.-$O(2^{(1-ε)n})$ circuits, do we get $\mathrm{BPTime}(O(n^a))⊂\mathrm{Time}(O(n^{2a+ε}))$? If not, what is the best known Time bound here? (If 'worst-case hard' to 'pseudorandom' conversion can be done efficiently, a prng against $\mathrm{Size}(n^a)$ uses a length $\mathrm{lg}(n^{a+ε})$ seed (without uniformity, $\mathrm{lg}(n^{a-ε})$ does not suffice), leading to $\mathrm{Time}(\tilde{O}(n^{2a+ε}))$ to iterate over the seeds.)

Below is what I know.

Based on circumstantial evidence, a reasonable guess is that
- $\mathrm{Time}(O(n^a)) ⊄ \mathrm{BPTime}(O(n^{a-ε}))$
- $\mathrm{BPTime}(O(n^a))⊄\mathrm{Time}(O(n^{a+1-ε}))$
- $\mathrm{BPTime}(\tilde{O}(n^a))⊂\mathrm{Time}(\tilde{O}(n^{a+1}))$ or the weaker $\mathrm{BPTime}(\tilde{O}(n^a))⊂\mathrm{Time}(\tilde{O}(n^{2a}))$.
Intuitively, randomness is useful when there is an adversary, and to a limited extent, a problem instance can act as an adversary.

If pseudorandom generators (prng) are as easily constructible as possible, we get $\mathrm{BPTime}(\tilde{O}(n^a))⊂\mathrm{Time}(\tilde{O}(n^{a+1}))$: Run the BPTime machine with a prng $\tilde{O}(n)$ times to get (for example) $2^{-10n}$ error probability, and hardcode any exceptions (an infinite number would violate a form of pseudorandomness).

Furthemore, in $\mathrm{Time}(\tilde{O}(n^a))$, we can iterate over $ω(\log n)$ seeds, so under a strong derandomization assumption (that holds relative to a random oracle), an adversary needs superpolynomial time to find inputs where the deterministic algorithm fails. (The adversary controls the input $x$ (of length $n$) and can run the prng (which uses $x$), but the prng still appears sufficiently random relative to $x$. Using known cryptographic functions, we have plausible candidates for making $n^a ω(\log n)$ pseudorandom bits in $\tilde{O}(n^a)$ time using the input $x$ (of length $n$) that work for $O(n^a)$ (without the tilde) computations using $x$, despite the polynomially bounded adversary choosing $x$.)

As for $\mathrm{BPTime}(O(n^a))⊄\mathrm{Time}(O(n^{a+1-ε}))$, there are three lines of evidence:

  • Simple derandomization using a prng does not work here.

  • If the problem uses $O(n / \log n)$ cryptographic blackboxes, and we are promised that either none or most have a yes answer, and opening a blackbox takes $O(n^a)$ compute (that cannot be used for anything else), then we have a randomized $O(n^a)$ algorithm but not a deterministic $O(n^{a+1-ε})$ algorithm for detecting a yes answer. Relative to a random oracle, a similar construction works for (relativized) Promise-BPTime and probabilistic approximation problems.

  • Under NSETH, $\mathrm{BPTime}(O(n))⊄\mathrm{NTime}(O(n^{2-ε}))$. This appies even to $\mathrm{coRPTime}(O(n))$ with $O(\log n)$ randomness.

Nondeterministic Strong Exponential Time Hypothesis (NSETH) asserts that for every $ε>0$, there is $k$ such that $k$-TAUT (the complement of $k$-SAT) is not in $\mathrm{NTime}(O(2^{(1-ε)n}))$ ($n$ is the number of variables; the number of clauses is poly(n), though $\tilde{O}(n)$ might suffice). A nonuniform strengthening asserts that $k$-TAUT does not have nondeterministic i.o.-$O(2^{(1-ε)n})$ circuits. The strengthening implies that $\mathrm{BPTime}(O(n))$ (or just $\mathrm{coRPTime}(O(n))$ with $O(\log n)$ randomness) does not have nondeterministic i.o.-$O(n^{2-ε})$ circuits. However, the plausibility of NSETH is not clear, and especially its non-uniform strengthening perhaps sounds too strong to be true. The connection of NSETH with BPTime is proved in (Williams 2016).

Note: In fine-grained complexity, $\mathrm{Time}$ usually refers to RAM-based machines, but the above discussion also applies to multitape Turing machines.

  • $\begingroup$ I’m curious if these can resolved in an oracle setting by using two oracles at a time, to represent a BPP machine being able to handle random queries against any oracle but a P machine only handling the one oracle it has. $\endgroup$ Jun 8, 2020 at 16:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.