Pseudodeterministic constructions in subexponential time
Pseudodeterministic constructions in subexponential time
复制标题
次指数时间内的伪确定性构造
DOI：
10.1145/3055399.3055500
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Santhanam
中科院分区：
文献类型：
--
作者：
I. Oliveira;R. Santhanam
我们研究伪确定性构造，即在大多数计算路径上输出相同解的随机化算法。我们无条件地证明了存在一个无限的素数序列{pn}和一个随机算法A在期望的次指数时间内运行，使得对于每个n，在输入1|pn|上，A以概率1输出pn。换句话说，我们的结果提供了一个在次指数时间内的素数的伪确定性构造，它经常工作。这一结果源于关于伪确定性结构的一个更一般的定理。性质Q⊆{0，1}*是ϒ稠密的，如果对足够大的n，|Q∩{0，1}n|≥ϒ2n。我们证明了对于每个C>；至少下列条件之一成立：(1)存在集族{hn}的伪确定性多项式时间构造，Hn⊆{0，1}n，使得对于每个(1/Nc)-稠密性质QΕDTime(Nc)和每个足够大的n，Hn∩Q≠∅或(2)存在集族{H‘n}的确定性亚指数时间构造，H’n∩{0，1}n，使得对于每个(1/Nc)稠密性质QΕDTime(Nc)和对于n的无穷多个值，H‘n∩Q≠∅.我们提供可能独立感兴趣的进一步的算法应用程序。也许有趣的是，虽然我们的主要结果是无条件的，但它们有一个非建设性的因素，源于对硬性与随机性范式的一系列应用。
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} of 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 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.
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David