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 \in \mathbb{ N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input $1^{ |p_n|}$, $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 \subseteq \{ 0,1\}^{ *}$ is $\gamma$-dense if for large enough $n$, $|Q \cap \{ 0,1\}^n| \geq \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 \subseteq \{ 0,1\}^n$, such that for each $(1/n^c)$-dense property $Q \in \mathsf{ DTIME}(n^c)$ and every large enough $n$, $H_n \cap Q \neq \emptyset$; or (2) There is a deterministic sub-exponential time construction of a family $\{ H'_n\}$ of sets, $H'_n \subseteq \{ 0,1\}^n$, such that for each $(1/n^c)$-dense property $Q \in \mathsf{ DTIME}(n^c)$ and for infinitely many values of $n$, $H'_n \cap Q \neq \emptyset$. 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.
Categories: cs.CC cs.DM cs.DS math.CO math.NT