Collaborative Research: Understanding, Coping with, and Benefiting from Intractibility.

合作研究：理解、应对棘手问题并从中受益。

• 批准号: 0832797
• 负责人: Sanjeev Arora
• 金额: $ 686.8万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-15 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0832797&HistoricalAwards=false
• 关键词: Collaborative; Research; Understanding; Coping; Benefiting

Expeditions in Computing: Understanding, Coping with, and Benefiting from Intractability Computational intractability imposes a limit on the ability to understand nature and design systems. Intractability is a stumbling block for postmen, travelling salesmen, map colorers, and millions of others who would like to complete their tasks as efficiently as possible, yet it is the foundation of 21st century cryptography, which in turn is a pillar of electronic commerce. In order to understand, manage, and exploit intractability it is imperative that progress be made on proving intractability in many forms and computational models, and on unraveling the interconnections among different forms and uses of intractability. This Expedition will explore an array of diverse but interrelated topics in computational intractability including algorithms, complexity, cryptography, analysis, geometry, combinatorics, and quantum mechanics. A "Center for Intractability," the first of its kind, will be based at Princeton. Addressing some of the deepest and hardest theoretical problems standing in the way of significant advancements in computer science, this Expedition involves a high degree of collegial interactivity through collaborations among geographically local participating institutions. Outreach includes an active "Women in Theory" program as well as programs targeting undergraduate and high-school students.

计算探索：理解、处理和受益于困难计算困难对理解自然和设计系统的能力造成了限制。困难是邮递员、旅行推销员、地图绘图员和数百万其他希望尽可能高效地完成任务的人的绊脚石，但它是21世纪密码学的基础，而密码学又是电子商务的支柱。为了理解、管理和开发难解性，必须在以多种形式和计算模型证明难解性方面取得进展，并在解开难解性不同形式和用途之间的相互联系方面取得进展。这次探险将探索一系列不同但相互关联的计算难题，包括算法、复杂性、密码学、分析、几何、组合学和量子力学。“棘手中心”将设在普林斯顿，这是第一个这样的中心。为了解决阻碍计算机科学取得重大进展的一些最深层次和最困难的理论问题，本次考察队通过在地理位置不同的参与机构之间的合作，进行了高度的大学互动。外展活动包括一个积极的“理论中的女性”项目，以及针对本科生和高中生的项目。