Zero knowledge and circuit minimization
Zero knowledge and circuit minimization
复制标题
零知识和电路最小化
DOI：
10.1016/j.ic.2017.04.004
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Bireswar Das
中科院分区：
文献类型：
--
作者：
Eric Allender;Bireswar Das
我们表明，每个问题的复杂性类SZK（统计零知识）是有效地减少到最小电路尺寸问题（MCSP）。特别是图同构在于RP MCSP。这是与图同构和MCSP的计算能力相关的第一个定理，尽管这些问题共享了很长的历史，作为候选NP-中间问题。
We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP MCSP. This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these problems share, as candidate NP-intermediate problems.