  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.

Computational Complexity;Discrete Mathematics;Data Structures and Algorithms;Combinatorics;Number Theory