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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.