Research Into the Complexity Theory of Games and Polynomials

博弈与多项式复杂性理论研究

• 批准号: 0431023
• 负责人: Richard Lipton
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0431023&HistoricalAwards=false
• 关键词: Research; Into; Complexity; Theory; Games

We propose to work on several areas of theory. The first concerns gametheoretic/economic questions. The second concerns several questions aboutpolynomials: zero testing, MOD complexity, and learning.The proposed research will examine a variety of open problems fromthese areas. Some of the open problems are classic and well known;others are new. The mix between known problems that are oftendifficult and new problems is important. Both types of problems will,we believe, advance our understanding of these important questions.The first questions concern mainly non-cooperative games as well asfair division problems. These problems have often been studied foryears, but only recently have researchers looked closely at theircomputational complexity. It seems clear that the interface betweengame theory and economic problems with complexity theory hastremendous potential.The second questions concern mainly classic problems from thefoundations of complexity theory. They include the power of polynomialunder various complexity restrictions and certain learningproblems. The problems are important for two reasons. They areimportant for their own sake. Further, their solution or even partialsolution is likely to yield new insights and potentially newtechniques. These could then be used to further our understanding ofother problems in other parts of theory.Intellectual Merit: Games and economic problems are extremelychallenging. This is especially true for non-zero sum games. Theircomplex structure raises many important fundamental questions. Weexpect to learn a great deal from the study of these importantproblems. This is also true for the more classic questions concerningpolynomials. The questions of testing, mod behavior, and learning aredifficult problems. Some have been challenging open problems fordecades. We believe that any progress on these problems will requireus to use old methods in new ways and to invent new methods.Broader Impact: The impact of the proposed research into gamesand economic problems is clear. Progress on the computational aspectsof economic problems has a clear impact on society. As commercebecomes more digital, it is clear that any better understanding of gamesand economic problems will have impact on a very broad community.The work on polynomials also will have a broad impact. Some of themost fundamental theory questions would be effected by progress on anyof the proposed research. The impact would be far beyond the theorycommunity that studies these questions. It could effect other fieldslike: cryptography, learning theory, and fundamental parts ofmathematics.

我们建议在几个理论领域开展工作。第一个问题涉及博弈论/经济问题。第二个是关于多项式的几个问题：零测试、MOD复杂度和学习。拟议的研究将检查这些领域的各种悬而未决的问题。一些开放问题是经典的和众所周知的；还有一些是新的。通常困难的已知问题和新问题之间的混合很重要。我们相信，这两类问题将促进我们对这些重要问题的理解。第一个问题主要涉及非合作博弈和公平分配问题。这些问题通常已经研究了多年，但直到最近，研究人员才仔细研究了它们的计算复杂性。显然，博弈论与复杂性理论的经济问题之间的接口具有巨大的潜力。第二个问题主要涉及复杂性理论基础中的经典问题。它们包括多项式在各种复杂性限制下的能力和某些学习问题。这些问题之所以重要，有两个原因。它们本身就很重要。此外，他们的解决方案甚至部分解决方案可能产生新的见解和潜在的新技术。这些可以用来进一步理解理论中其他部分的其他问题。智力优势：游戏和经济问题极具挑战性。对于非零和博弈尤其如此。它们复杂的结构提出了许多重要的基本问题。我们期望从这些重要问题的研究中学到很多东西。对于更经典的多项式问题也是如此。测试、建模行为和学习的问题是困难的问题。有些人几十年来一直在挑战开放性问题。我们认为，在这些问题上取得任何进展都需要以新的方式使用旧的方法，并发明新的方法。更广泛的影响：对游戏和经济问题的拟议研究的影响是显而易见的。经济问题的计算方面的进步对社会有明显的影响。随着商业变得更加数字化，很明显，任何对游戏和经济问题的更好理解都将对一个非常广泛的社区产生影响。对多项式的研究也将产生广泛的影响。一些最基本的理论问题将受到任何拟议研究进展的影响。其影响将远远超出研究这些问题的理论界。它可能会影响到其他领域，比如密码学、学习理论和数学的基本部分。