Randomness in Computation and Proof

计算和证明中的随机性

• 批准号: 9503322
• 负责人: Michael Sipser
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-09-01 至 1999-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9503322&HistoricalAwards=false
• 关键词: Randomness; Computation; Proof

This research aims to further our understanding of the interplay between randomness and computation in complexity theory. The investigation concentrates on aspects of interactive proof systems, probabilistically checkable proofs, the approximability of problems in combinatorial optimization, and related areas. One goal is to examine several ways in which construction of probabilistically checkable proofs may be improved and in so doing strengthen the derived lower bounds on approximability. In addition, a study is planned of useful structures that may be suggested by these constructions, such as error-correcting codes with novel properties. Other goals are to investigate reducibility among probabilistic constructions and to consider the possibility that there are objects that are universal for such constructions.

这项研究旨在进一步了解复杂性理论中随机性和计算之间的相互作用。 调查集中在交互式证明系统，概率可检查的证明，在组合优化问题的近似性方面，以及相关领域。 一个目标是研究几种方法，其中建设的概率可检查的证据可能会得到改善，并在这样做加强推导的下界逼近。 此外，还计划对这些结构可能提出的有用结构进行研究，例如具有新特性的纠错码。 其他的目标是研究概率结构之间的约简，并考虑是否存在对这种结构具有普适性的对象。