2016/12/06 by Igor Carboni Oliveira, Oliveira, Igor C., Rahul Santhanam +1 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1612.01817
We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infinite sequence \pn\n ∈ ℕ of increasing primes and a randomized algorithm A running in expected sub-exponential time such that for each n, on input 1|pn|, A outputs pn with probability 1. In other words, our result provides a pseudodeterministic construction of primes in sub-exponential time which works infinitely often. This result follows from a much more general theorem about pseudodeterministic constructions. A property Q ⊆ \0,1\* is γ-dense if for large enough n, |Q ∩ \0,1\n| ≥ γ2n. We show that for each c > 0 at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family \Hn\ of sets, Hn ⊆ \0,1\n, such that for each (1/nc)-dense property Q ∈ DTIME(nc) and every large enough n, Hn ∩ Q ≠ ∅; or (2) There is a deterministic sub-exponential time construction of a family \H'n\ of sets, H'n ⊆ \0,1\n, such that for each (1/nc)-dense property Q ∈ DTIME(nc) and for infinitely many values of n, H'n ∩ Q ≠ ∅. We provide further algorithmic applications that might be of independent interest. Perhaps intriguingly, while our main results are unconditional, they have a non-constructive element, arising from a sequence of applications of the hardness versus randomness paradigm.