The complexity of estimating min-entropy
The complexity of estimating min-entropy
复制标题
估计最小熵的复杂性
DOI：
--
复制
发表时间：
2016
影响因子：
1.4
通讯作者：
Thomas Watson
中科院分区：
文献类型：
--
作者：
Thomas Watson
Goldreich等。 ，即使采样电路被限制为3局，SBP是与NP证人的近似计数相对应的对数空间样本，我们观察到，由于Lyngsø和Pedersen在隐藏的Markov模型上的结果是NP的完整（JCSS 65（3）：545–569，2002）。
Goldreich et al. (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, where SBP is the class of promise problems that correspond to approximate counting of NP witnesses. The result holds even when the sampling circuits are restricted to be 3-local. For logarithmic-space samplers, we observe that this problem is NP-complete by a result of Lyngsø and Pedersen on hidden Markov models (JCSS 65(3):545–569, 2002).