内容説明
"The Power of Interaction" presents a new algebraic technique for constructing interactive proof systems and demonstrates the immense power of randomization and interaction in proving statements efficiently. Lund shows that two provers can interact with a randomized verifier to provide proofs that are exponentially more efficient than traditional proofs, and that one power can interact with an efficient randomized verifier to prove statements that have no known efficient traditional proofs.
目次
- 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.
「Nielsen BookData」 より