Pseudodeterministic algorithms and the structure of probabilistic time
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam · 2021
We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of BPTIME: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.