The power of interaction
The power of interaction
复制标题
互动的力量
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
C. Lund
中科院分区：
文献类型：
--
作者：
C. Lund
Part 1 Preliminaries: basic definitions - notation and basics, Boolean formulas, arithmetic formulas and expressions computational models - deterministic computation, probabilistic computation, non-deterministic computation, alternating computation, interactive proof system, multiple prover interactive proof systems computation relative to an oracle complexity classes - deterministic complexity classes, probabilistic complexity classes, non-deterministic complexity clases, alternatiing complexity classes, interactive proof system complexity classes, non-uniform complexity classes, complexity classes relative to oracles counting clases completeness summary of our results. Part 2 The power of interaction with one prover: proof systems for #P - arithmetizing of #P, proof systems for #P proof systems for PSPaCE - arithmetizing of PSPACE, proof systems for PSPACE. Part 3 The power of interaction with two provers: another characterization of MIP arithmetization of NEXP computation multiple prover interactive proofs for NEXP - implementing the protocol with two provers, the power of the provers verification of multilinear functions - the test for multilinearity, the expansion Lemma, the self-improvement Lemma, the pasting Lemma, the tree colouring Lemma. Part 4 Interaction versus alternation: restricted alternating turing machines arithmetization of alternating computation interactive proof systems for ATISP (t,s) alternating turing machines for pIPTISP(t,s) a hierarchy for pIPTISP(t,s) interactive proof systems for deterministic computation. Part 5 Implications and open problems: bounded-round interactive proofs zero-knowledge program testing and verification - robustness, instance checking, self-testing and self-correcting programs, comparison with the Blum-Luby-Rubinfield model uniform vs. nonuniform complexity recent developments further research.
