A short note on Merlin-Arthur protocols for subset sum
A short note on Merlin-Arthur protocols for subset sum
复制标题
DOI：
10.1016/j.ipl.2016.09.002
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Jesper Nederlof
中科院分区：
文献类型：
--
作者：
Jesper Nederlof
在子集求和问题中，给出了n个正整数和一个目标整数t。解是这些正整数求和到t的子集。在这个简短的注解中，我们证明了对于给定的子集和实例，有多少解的大小的证明可以及时构造，并且可以以最大恒定的错误概率在时间上被概率地验证。这里，表示法省略了输入大小中的因子多项式。
In the subset sum problem we are given n positive integers along with a target integer t. A solution is a subset of these integers summing to t. In this short note we show that for a given subset sum instance there is a proof of sizeof what the number of solutions is that can be constructed intime and can be probabilistically verified in timewith at most constant error probability. Here, thenotation omits factors polynomial in the input size.