5
$\begingroup$

Under $BPP=P$ conjecture randomization does not have much power for poly time algorithms.

Can we say the same about randomized subexp algorithms like number field sieve?

$\endgroup$
  • 1
    $\begingroup$ Have you tried the padding trick? Pad the input so that the algorithm now runs in polynomial time, derandomize it, and then "unpad". $\endgroup$ – Yuval Filmus Apr 2 '16 at 22:34
  • $\begingroup$ @YuvalFilmus aha so randomized algorithms can always be derandomized (no matter running time)? $\endgroup$ – user39969 Apr 2 '16 at 22:37
  • $\begingroup$ Padding only works in one direction, though. Try to write this argument formally, and so answer your own question. Also, when I say "derandomize", I mean use the conjecture $P=BPP$. Everything is conditional anyhow. $\endgroup$ – Yuval Filmus Apr 2 '16 at 22:38
  • $\begingroup$ @YuvalFilmus When you say padding this is what i understand. pad input to make longer so subexp becomes poly in new input and $P=BPP$ implies randomization is not powerful for this new input and removing padding implies $BPSUBEXP$ is same as $SUBEXP$. $\endgroup$ – user39969 Apr 2 '16 at 22:42
  • 1
    $\begingroup$ Right, that's the idea. $\endgroup$ – Yuval Filmus Apr 2 '16 at 22:43
3
$\begingroup$

Derandomization results transfer "upwards" using the technique of padding. Assume $\mathsf{P}=\mathsf{BPP}$. Suppose that some problem $A$ can be solved in randomized superpolynomial time $t(n)$ (which is time-constructible). Let $A'$ be the same problem, but with inputs padded to length $t(n)$. Then $A' \in \mathsf{BPP} = \mathsf{P}$. The following algorithm then solves $A$ in deterministic time $t(n)$: pad the input to length $t(n)$, then apply the polynomial time algorithm for $A'$.

Conversely, it is possible (given the current state of knowledge) that subexponential time algorithms can be randomized, but polynomial time algorithms can't (and it might be possible to construct a relativized world in which this happens unconditionally). That is, results don't transfer "downwards".

$\endgroup$

Your Answer

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