Pseudodeterministic Constructions in Subexponential Time

We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infinite sequence {p(n)}(n)is an element of N of increasing primes and a randomized algorithm A running in expected sub-exponential time such that for each n, on input 1 vertical bar p(n)vertical bar, A outputs p(n) with probability 1. In other words, our result provides a pseudodeterministic construction of primes in sub-exponential time which works infinitely often. This result follows from a much more general theorem about pseudodeterministic constructions. A property Q subset of {0, 1}* is gamma-dense if for large enough n, vertical bar Q boolean AND {0, 1}(n)vertical bar >= gamma 2 (n). We show that for each c > 0 at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family {H-n} of sets, H-n subset of {0, 1}(n), such that for each (1/n(c))-dense property Q is an element of DTIME (n(c)) and every large enough n, H-n boolean AND Q not equal empty set or (2) There is a deterministic sub-exponential time construction of a family {H'(n)} of sets, H'(n) subset of {0, 1}(n), such that for each (1/n(c))-dense property Q is an element of DTIME (n(c)) and for infinitely many values of n, H'n boolean AND Q not equal empty set. We provide further algorithmic applications that might be of independent interest. Perhaps intriguingly, while our main results are unconditional, they have a non-constructive element, arising from a sequence of applications of the hardness versus randomness paradigm.