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?
$\begingroup$
$\endgroup$
9
-
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 FilmusCommented Apr 2, 2016 at 22:34
-
$\begingroup$ @YuvalFilmus aha so randomized algorithms can always be derandomized (no matter running time)? $\endgroup$– user39969Commented Apr 2, 2016 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 FilmusCommented Apr 2, 2016 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$– user39969Commented Apr 2, 2016 at 22:42
-
1$\begingroup$ Right, that's the idea. $\endgroup$– Yuval FilmusCommented Apr 2, 2016 at 22:43
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
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".
answered Apr 3, 2016 at 9:59