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...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for Computing Machinery
2021
|
| _version_ | 1797102543889760256 |
|---|---|
| author | Lu, Z Oliveira, IC Santhanam, R |
| author_facet | Lu, Z Oliveira, IC Santhanam, R |
| author_sort | Lu, Z |
| collection | OXFORD |
| description | 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 generator and its consequences. We build on techniques developed to prove hierarchy theorems for probabilistic time with advice (Fortnow and Santhanam [FS04]) to construct an unconditional pseudorandom generator 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. For instance, we show unconditionally for each ε > 0 that infinitely many primes p_n have a succinct representation in the following sense: there is a fixed probabilistic polynomial time algorithm that generates p_n with high probability from its succinct representation of size O(|p_n|^ ε). This offers an exponential improvement over the running time of previous results, and shows that infinitely many primes have succinct and efficient representations.
<br>
Structural results for probabilistic time from improved pseudo-deterministic algorithms. Oliveira and Santhanam [OS17] established unconditionally that there is a pseudodeterministic algorithm for the Circuit Acceptance Probability Problem (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 CAPP would imply that BPP has complete problems.
<br>
Equivalences. We establish an equivalence between a certain explicit pseudodeterministic construction problem and the existence of strong hierarchy theorems for probabilistic time. More
precisely, we show that pseudodeterministically constructing in exponential time strings of large rKt complexity (Oliveira [Oli19]) is possible if and only if for every constructive function T(n) ≤ exp(o(exp(n))) we have BPTIME[poly(T)] * i.o.BPTIME[T]/ log T.
<br>
More generally, these results suggest new approaches for designing pseudodeterministic algorithms for search problems and for unveiling the structure of probabilistic time.
|
| first_indexed | 2024-03-07T06:07:24Z |
| format | Conference item |
| id | oxford-uuid:ee547a21-e2b0-416f-9b14-6f3025f2bc49 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:07:24Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:ee547a21-e2b0-416f-9b14-6f3025f2bc492022-03-27T11:31:46ZPseudodeterministic algorithms and the structure of probabilistic timeConference itemhttp://purl.org/coar/resource_type/c_5794uuid:ee547a21-e2b0-416f-9b14-6f3025f2bc49EnglishSymplectic ElementsAssociation for Computing Machinery2021Lu, ZOliveira, ICSanthanam, RWe 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 generator and its consequences. We build on techniques developed to prove hierarchy theorems for probabilistic time with advice (Fortnow and Santhanam [FS04]) to construct an unconditional pseudorandom generator 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. For instance, we show unconditionally for each ε > 0 that infinitely many primes p_n have a succinct representation in the following sense: there is a fixed probabilistic polynomial time algorithm that generates p_n with high probability from its succinct representation of size O(|p_n|^ ε). This offers an exponential improvement over the running time of previous results, and shows that infinitely many primes have succinct and efficient representations. <br> Structural results for probabilistic time from improved pseudo-deterministic algorithms. Oliveira and Santhanam [OS17] established unconditionally that there is a pseudodeterministic algorithm for the Circuit Acceptance Probability Problem (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 CAPP would imply that BPP has complete problems. <br> Equivalences. We establish an equivalence between a certain explicit pseudodeterministic construction problem and the existence of strong hierarchy theorems for probabilistic time. More precisely, we show that pseudodeterministically constructing in exponential time strings of large rKt complexity (Oliveira [Oli19]) is possible if and only if for every constructive function T(n) ≤ exp(o(exp(n))) we have BPTIME[poly(T)] * i.o.BPTIME[T]/ log T. <br> More generally, these results suggest new approaches for designing pseudodeterministic algorithms for search problems and for unveiling the structure of probabilistic time. |
| spellingShingle | Lu, Z Oliveira, IC Santhanam, R Pseudodeterministic algorithms and the structure of probabilistic time |
| title | Pseudodeterministic algorithms and the structure of probabilistic time |
| title_full | Pseudodeterministic algorithms and the structure of probabilistic time |
| title_fullStr | Pseudodeterministic algorithms and the structure of probabilistic time |
| title_full_unstemmed | Pseudodeterministic algorithms and the structure of probabilistic time |
| title_short | Pseudodeterministic algorithms and the structure of probabilistic time |
| title_sort | pseudodeterministic algorithms and the structure of probabilistic time |
| work_keys_str_mv | AT luz pseudodeterministicalgorithmsandthestructureofprobabilistictime AT oliveiraic pseudodeterministicalgorithmsandthestructureofprobabilistictime AT santhanamr pseudodeterministicalgorithmsandthestructureofprobabilistictime |