Threshold Computation and Cryptographic Security
Threshold Computation and Cryptographic Security
复制标题
阈值计算和密码安全
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
T. Thierauf
中科院分区：
文献类型：
--
作者：
Yenjo Han;L. Hemaspaandra;T. Thierauf
阈值机器[21]是图灵机，其接受是由机器计算路径的哪一部分接受路径的确定。概率机器[11]是图灵机，其接受是由机器接受计算路径的概率重量决定的。 Simon [21]证明，对于无界错误的多项式计算机，这两个概念产生了同一类，PP。也许是因为西蒙的结果似乎崩溃了计算的阈值和概率模式，因此对于有界误差的情况下，阈值和概率计算之间的关系仍未得到探索。
Threshold machines [21] are Turing machines whose acceptance is determined by what portion of the machine's computation paths are accepting paths. Probabilistic machines [11] are Turing machines whose acceptance is determined by the probability weight of the machine's accepting computation paths. Simon [21] proved that for unbounded-error polynomial-time machines these two notions yield the same class, PP. Perhaps because Simon's result seemed to collapse the threshold and probabilistic modes of computation, the relationship between threshold and probabilistic computing for the case of bounded error has remained unexplored.