Short PCPPs verifiable in polylogarithmic time with O(1) queries
Short PCPPs verifiable in polylogarithmic time with O(1) queries
复制标题
可通过 O(1) 查询在多对数时间内验证短 PCPP
DOI：
--
复制
发表时间：
2009
影响因子：
1.2
通讯作者：
Thilo Mie
中科院分区：
文献类型：
--
作者：
Thilo Mie
In this paper we show for every pair language $Lsubseteq {0,1}^* imes{0,1}^*$ in ${ensuremath{mathsf{NTIME}}}(T)$ for some non-decreasing function $T:{{mathbb Z}}^+
ightarrow {{mathbb Z}}^+$ there is a ${ensuremath{mathsf{PCPP}}}$-verifier such that the following holds. In time poly (|x|,log|y|,logT(|x| + |y|)) it decides the membership of a purported word (x,y) by reading the explicit input x entirely and querying the implicit input y and the auxiliary proof of length T(|x| + |y|)·poly log T(|x| + |y|) in a constant number of positions.
In this paper we show for every pair language $Lsubseteq {0,1}^* imes{0,1}^*$ in ${ensuremath{mathsf{NTIME}}}(T)$ for some non-decreasing function $T:{{mathbb Z}}^+
ightarrow {{mathbb Z}}^+$ there is a ${ensuremath{mathsf{PCPP}}}$-verifier such that the following holds. In time poly (|x|,log|y|,logT(|x| + |y|)) it decides the membership of a purported word (x,y) by reading the explicit input x entirely and querying the implicit input y and the auxiliary proof of length T(|x| + |y|)·poly log T(|x| + |y|) in a constant number of positions.