  We connect the study of pseudodeterministic algorithms to two major open
problems about the structural complexity of $\mathsf{BPTIME}$: proving
hierarchy theorems and showing the existence of complete problems. Our main
contributions can be summarised as follows.
  1. We build on techniques developed to prove hierarchy theorems for
probabilistic time with advice (Fortnow and Santhanam, FOCS 2004) to construct
the first unconditional pseudorandom generator of polynomial stretch computable
in pseudodeterministic polynomial time (with one bit of advice) that is secure
infinitely often against polynomial-time computations. As an application of
this construction, we obtain new results about the complexity of generating and
representing prime numbers.
  2. Oliveira and Santhanam (STOC 2017) established unconditionally that there
is a pseudodeterministic algorithm for the Circuit Acceptance Probability
Problem ($\mathsf{CAPP}$) that runs in sub-exponential time and is correct with
high probability over any samplable distribution on circuits on infinitely many
input lengths. We show that improving this running time or obtaining a result
that holds for every large input length would imply new time hierarchy theorems
for probabilistic time. In addition, we prove that a worst-case polynomial-time
pseudodeterministic algorithm for $\mathsf{CAPP}$ would imply that
$\mathsf{BPP}$ has complete problems.
  3. We establish an equivalence between pseudodeterministic construction of
strings of large $\mathsf{rKt}$ complexity (Oliveira, ICALP 2019) and the
existence of strong hierarchy theorems for probabilistic time.
  More generally, these results suggest new approaches for designing
pseudodeterministic algorithms for search problems and for unveiling the
structure of probabilistic time.
