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.

计算复杂性理论的研究：项目摘要计算复杂性理论的重点是理解资源有限计算的功能。置于统一的计算，作为统一计算（基于图灵机器）和非统一计算（基于电路）。所研究的典型资源是用于均匀计算的时间步骤和内存空间，以及用于非均匀计算的电路大小和深度。通过将计算的各种资源要求限制在某些强大的界限上，我们将获得ComplectityClasses，这是复杂性理论中研究的基本对象。复杂性理论的研究广泛地围绕两个主题（1）在各种复杂性类别中以包含和分离的形式证明关系（2）使用计算机来量化di.culty/siseiness量化的习惯/易于解决现实的计算问题。这两个主题与完整性和降低的概念相互联系。该提案的总体目标是沿这两个主题推进计算复杂性理论。总体目标将通过三个目标来实现：目标1：研究均匀性，非均匀性和降低的相互关系。PI将研究统一与非统一计算中的许多问题，以及它们与降低的关系的关系。特定地说，PI将研究Arthur-Merlin游戏的统一性化，一些相关的非统一性问题，包括具有高电路复杂性的语言的统一上行，以及​​某些基于覆盖的资源措施的方法，用于较低的复杂性类别和贬值。目标2：研究中间复杂性的计算问题。 PI将他对P和NP完整的Suchas Graph同构问题和某些计算组理论问题之间的问题进行调查。将研究与这些问题的lowness属性有关的数字问题。 E. corientprogron Checker将设计许多计算群体理论问题。目标3：探索复杂性理论与计算差异理论之间的互连。 PI将探索复杂性理论与学习理论之间的互连。特别是，PI将调查学习问题，例如在助教模型中学习DNFS和Boolean Circuits，以及学习算法复杂性理论的应用。BROADER的影响：拟议的研究活动将产生一些更广泛的影响。复杂性理论间接影响计算机科学的许多领域。因此，拟议的研究具有潜在的toscienti。对这些领域产生影响。这笔赠款的研究结果将在同行评审的journals中发表，并将在国际会议上提出，从而使您对这一结果的广泛传播以增强Scienti.c的理解。将在该项目的thetheme上创建和教授新课程，从而整合教学和研究。该赠款还将用于各种人类的资源开发活动，例如支持和指导研究生，以及引起访客。智能优点：复杂性理论取得的进步对于通过使用合理资源来推动计算机可以解决的知识和无法解决的知识至关重要。从该提案中的结果将扩展我们对复杂性理论的知识。研究依赖化和非均匀性将解决一些重要的问题。该地区的开放问题，将有助于更好地了解随机性在计算中的作用。提议研究的一部分直接涉及重要的现实生活问题，例如图形同构问题和DNF学习问题，并且有可能实际上适用。关于程序检查员的研究预计将具有一些实际应用。