Studies in Computational Complexity Theory

计算复杂性理论研究

• 批准号: 0430991
• 负责人: Vinodchandran Variyam
• 金额: $ 20万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-01 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430991&HistoricalAwards=false
• 关键词: Studies; Computational; Complexity; Theory

Studies in Computational Complexity Theory: Project SummaryComputational complexity theory focuses on understanding capabilities of resource bounded computations.Computations are broadly classi.ed as uniform computations (Turing machine based)and non-uniform computations (circuit based). Typical resources studied are time steps and memoryspace for uniform computations, and circuit size and depth for non-uniform computations. Bylimiting various resource requirements of computations to certain robust bounds we get complexityclasses, which are the fundamental objects of study in complexity theory. Research in complexitytheory broadly centers around two themes (1) proving relations, in the form of inclusions and separations,among various complexity classes (2) quantifying the di.culty/easiness of solving real-lifecomputational problems using a computer. These two themes are interconnected by the notionsof completeness and reductions. The overall goal of this proposal is to advance computationalcomplexity theory along these two themes. The overall goal will be accomplished through threerelated objectives:Objective 1: Investigate interrelations among uniformity, nonuniformity, and derandomization.The PI will investigate a number of issues in uniform vs non-uniform computations andtheir relation to derandomization. Speci.cally, the PI will investigate uniform derandomizationof Arthur-Merlin games, some related non-uniformity questions including uniform upperbounds for languages with high circuit complexity, and certain cover-based approach to resourcebounded measure with applications to lower complexity classes and derandomization.Objective 2: Investigate computational problems with intermediate complexity. The PI willcontinue his investigation of problems that are intermediate between P and NP-complete suchas Graph Isomorphism problem and some computational group-theoretic problems. A numberof questions related to lowness properties of these problems will be investigated. E.cientprogram checkers for a host of computational group-theoretic problems will be designed.Objective 3: Explore the interconnections between complexity theory and computationallearning theory. The PI will explore interconnections between complexity theory and learningtheory. In particular, the PI will investigate learning problems such as learning DNFs andBoolean Circuits in the Teaching Assistant model, and the applications of learning algorithmsto complexity theory.Broader Impacts: The proposed research activity will have several broader impacts. Complexitytheory indirectly impacts many areas of computer science. Thus proposed research has potential toscienti.cally impact these areas. Research results from this grant will be published in peer-reviewedjournals and will be presented in international conferences, thus enabling broad dissemination of thethe results to enhance scienti.c understanding. New courses will be created and taught along thetheme of this project, thus integrating teaching and research. The grant will also be used for varioushuman resource development activities such as supporting and mentoring graduate students, andinviting visitors.Intellectual Merit: Progress made in complexity theory is essential for furthering the knowledgeof what can and cannot be solved by a computer using reasonable amount of resources. The resultsfrom this proposal will extend our knowledge of complexity theory in several directions. Researchin derandomization and non-uniformity will solve some signi.cant open problems in the area andwill contribute to better understand the role of randomness in computation. Part of the proposedresearch directly relates to important real-life problems such as Graph Isomorphism problem andDNF learning problem and has potential to become practically applicable. The research on programcheckers is expected to have some practical applications.

计算复杂性理论研究：项目综述计算复杂性理论侧重于理解资源受限计算的能力。计算大致分为统一计算(基于图灵机)和非统一计算(基于电路)。研究的典型资源是用于统一计算的时间步长和内存空间，以及用于非统一计算的电路大小和深度。通过将计算的各种资源需求限制在一定的健壮界内，我们得到了复杂性类，这是复杂性理论的基本研究对象。复杂性理论的研究主要围绕两个主题展开：(1)以包含和分离的形式证明各种复杂类别之间的关系；(2)量化使用计算机解决现实生活中计算问题的难易程度。这两个主题通过完整和减少的概念相互联系。这项提议的总体目标是沿着这两个主题推进计算复杂性理论。总体目标将通过三个相关的目标来实现：目标1：调查一致性、非一致性和去随机化之间的相互关系。PI将调查在均匀和非统一计算中的一些问题以及它们与去随机化的关系。具体地说，PI将研究Arthur-Merlin博弈的一致去随机化，一些相关的非一致性问题，包括具有高电路复杂性的语言的一致上界，以及某些基于覆盖的资源有界度量的应用，以及应用于低复杂度类和去随机化。目标2：研究中等复杂度的计算问题。PI将继续研究介于P和NP-完全之间的问题，如图同构问题和一些计算群论问题。我们将研究一些与这些问题的低性质有关的问题。目标3：探索复杂性理论和计算学习理论之间的内在联系。PI将探索复杂性理论和学习理论之间的相互联系。特别是，PI将调查学习问题，如在教学助理模型中学习DNF和布尔电路，以及学习算法在复杂性理论中的应用。广泛影响：拟议的研究活动将产生几个更广泛的影响。复杂性理论间接影响了计算机科学的许多领域。因此提出的研究有可能对这些领域产生科学影响。这笔赠款的研究成果将发表在同行评议的期刊上，并将在国际会议上发表，从而使这些成果得以广泛传播，以增进对科学的理解。将围绕该项目的主题创建和教授新课程，从而将教学和研究结合在一起。这笔赠款还将用于各种舒曼资源开发活动，如支持和指导研究生，邀请访问者。智力价值：复杂性理论取得的进展对于进一步了解什么是计算机可以解决的问题，什么是不能解决的问题，使用合理的资源至关重要。这一提议的结果将在几个方向上扩展我们对复杂性理论的认识。研究随机性和非均匀性将解决该领域中一些有意义的公开问题，有助于更好地理解随机性在计算中的作用。所提出的部分研究直接涉及到重要的现实问题，如图同构问题、DNF学习问题等，具有实际应用的潜力。程序检查器的研究可望具有一定的实际应用价值。