Abstrakt
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 of increasing primes and a randomized algorithm running in expected sub-exponential time such that for each , on input , outputs with probability.
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 is -dense if for large enough ,. We show that for each at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family of sets, , such that for each -dense property and every large enough , ; or (2) There is a deterministic sub-exponential time construction of a family of sets, , such that for each -dense property and for infinitely many values of ,.
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.