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\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^{\mathrm{\mid }{p}_n\mathrm{\mid }}$, $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{\}}^{\ast }$ is $\gamma$-dense if for large enough $n$, $\mathrm{\mid }Q\cap \{0,1{\}}^n\mathrm{\mid }\ge \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\mathrm{/}{n}^c)$-dense property $Q \in $\mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}$(n^c)$andeverylargeenough$n$,$H_n \cap Q \neq \emptyset$; or (2) There is a deterministic sub-exponential time construction of a family $\{H_n^{\mathrm{\prime }}\}$ of sets, $H_n^{\mathrm{\prime }}\subseteq \{0,1{\}}^n$, such that for each $(1\mathrm{/}{n}^c)$-dense property $Q\in \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(n^c)$ and for infinitely many values of $n$, $H_n^{\mathrm{\prime }}\cap Q\mathrm{\ne }\mathrm{\varnothing }$. 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.