Probabilistic Computation and Interactive Proof Systems

交互式证明系统由两个参与者组成，一个是“无限”强大的证明者，另一个是概率时间有限的验证者。证明者试图说服验证者相信某些陈述的正确性。然而，验证者不信任证明者，只有当证明者设法使验证者相信该陈述的有效性时，该验证者才会接受。证明者和验证者使用随机硬币与验证者对话，向证明者提问，直到验证者确信或不相信该陈述的有效性。这个项目将研究这些交互证明系统的复杂性，以及在最近的结果中使用的技术，表明在合理的空间内每一个可解决的问题都有这样的证明系统。这些新想法基于用简单的代数刻画来研究某些困难问题，可能会被证明对解决结构复杂性理论中的其他一些困难问题很有用。使用一定的密码假设，可以证明每个交互证明系统都有一个等价的零知识证明系统，即验证者除了声明是否有效外，不会从协议中获得任何信息。这个项目将尝试在没有任何密码学假设的情况下确定这样的定理是否正确。也许人们可以使用新的想法，使用某些不依赖于未知假设的“硬”函数来进行交互证明。这个项目还将研究一台可以访问随机硬币的计算机需要多长时间才能比一台类似的计算机以更少的时间实现更强大的功能。标准技术无助于解决这一问题，但也许用于交互证明系统的技术也可以证明这一问题。本项目还将研究多证明人交互证明系统的一些复杂性问题，其中有两个或多个证明人不能相互通信。虽然多证明者交互证明系统的复杂性是已知的，但本项目将研究这样的证明系统的复杂性，其中证明者和验证者之间的通信轮数不变，以及这些证明系统的各种应用的复杂性。

An interactive proof system consists of two players, an "infinitely" powerful prover and a probabilistic time-bounded verifier. The prover tries to convince the verifier of the validity of some statement. However, the verifier does not trust the prover and will only accept if the prover manages to convince the verifier of the validity of the statement. The prover and the verifier have a conversation with the verifier using random coins to ask questions to the prover until the verifier is or is not convinced of the validity of the statement. This project will examine the complexity of these interactive proof systems and the techniques used in the recent results showing every problem solvable in a reasonable amount of space has such a proof system. The new ideas, based on looking at certain hard problems with a simple algebraic characterization, may prove useful in tackling some of the other hard questions in structural complexity theory. Using certain cryptographic assumption, one can show every interactive proof system has an equivalent "zero-knowledge" proof system, i.e. the verifier receives no information from the protocol other than whether the statement was valid. This project will try to determine whether such a theorem is true without any cryptographic assumptions. Perhaps one could use the new ideas for interactive proofs using certain "hard" functions whose hardness do not depend on unknown assumptions. This project will also study how much more time is needed for a computer with access to random coins to be more powerful than a similar computer with less time. Standard techniques will not help to solve this problem but perhaps the techniques used for interactive proof systems may also prove this question. This project will also look at some complexity issues of multiple- prover interactive proof systems where there are two or more provers who can not communicate among themselves. While the complexity of multiple-prover interactive proof systems is known, this project will look at the complexity of such proof systems with a constant number of rounds of communication been the provers and the verifier and also various applications of the complexity of these proof systems.