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.