Pseudodeterministic algorithms and the structure of probabilistic time
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. <br> A new unconditional pseudorandom gen...
| Հիմնական հեղինակներ: | , , |
|---|---|
| Ձևաչափ: | Conference item |
| Լեզու: | English |
| Հրապարակվել է: |
Association for Computing Machinery
2021
|