Research Into the Complexity Theory of Games and Polynomials

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

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.