Pseudodeterministic Algorithms and the Structure of Probabilistic Time

Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam

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 e…