Pseudodeterministic algorithms and the structure of probabilistic time

DOI10.1145/3406325.3451085MaRDI QIDQ6087003zbMATH OpenOpenAlexFDO

Authors Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.08539, https://ora.ox.ac.uk/objects/uuid:ee547a21-e2b0-416f-9b14-6f3025f2bc49

zbMATH Keywords

hierarchy theoremsKolmogorov complexityprobabilistic timepseudodeterministic algorithmspseudorandom generators

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $mathsfBPTIME$: 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 ($mathsfCAPP$) 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 $mathsfCAPP$ would imply that $mathsfBPP$ has complete problems. 3. We establish an equivalence between pseudodeterministic construction of strings of large $mathsfrKt$ 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.

Recommendations

• On the possibilities and limitations of pseudodeterministic algorithms
• Polynomial time decision algorithms for probabilistic automata
• scientific article; zbMATH DE number 2019635
• Trading determinism for time in space bounded computations
• scientific article; zbMATH DE number 4205978
• Pseudodeterministic constructions in subexponential time
• Almost-everywhere complexity hierarchies for nondeterministic time
• Deterministic versus nondeterministic time and lower bound problems

Cited in

(13)

• Probabilistic weak simulation is decidable in polynomial time
• An algorithmic view of pseudochaos
• On the possibilities and limitations of pseudodeterministic algorithms
• scientific article; zbMATH DE number 4205978 (Why is no real title available?)
• New time hierarchy results for deterministic TMS
• On approximate majority and probabilistic time
• A duality between one-way functions and average-case symmetry of information
• Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
• Lower bounds for Levin-Kolmogorov complexity
• Polynomial-time pseudodeterministic construction of primes
• Oblivious complexity classes revisited: lower bounds and hierarchies
• On the expected time for Herman's probabilistic self-stabilizing algorithm

This page was built for publication: Pseudodeterministic algorithms and the structure of probabilistic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087003)