Research Into the Complexity Theory of Games and Polynomials

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

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.