AF: Medium: Algorithmic Complexity in Computation and Biology

AF：中：计算和生物学中的算法复杂性

• 批准号: 1509178
• 负责人: Leslie Valiant
• 金额: $ 90万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1509178&HistoricalAwards=false
• 关键词: AF; Medium; Algorithmic; Complexity; Computation

Computational complexity is the field that studies how much resources are needed for performing computational tasks. Its primary focus has been to understand how many steps and how much storage space is required for performing various important tasks on conventional computers. Biological processes, can also be viewed as computations to the extent that they consist of step-by-step processes that follow certain rules, and can then be also studied from the perspective of the theory of computational complexity. This proposal is concerned with studying both of these aspects. Its goal is that of proving, by mathematical means, upper or lower bounds on the resources needed for both general purpose and evolutionary computations. While much is understood about the complexity of computations on general purpose computers, this understanding is pivoted around a small number of critical open questions, such as the P=?NP question, the answer to which would resolve the resource requirements of numerous important tasks. The first focus of this study will be algebraic approaches to these questions, in which the limitations on computations imposed by algebraic axioms is analyzed. Holographic algorithms have over the last decade yielded novel algorithms for a variety of problems, as well as new lower bound arguments, and also new techniques for proving computational equivalence among apparently dissimilar problems. The goal of the research is to understand the inherent limits of holographic algorithms and to use this understanding to develop efficient algorithms. Darwinian evolution can be also viewed as a computational process that uses quantifiable resources, here measured in terms of numbers of generations, size of populations, and the number of experiences of individuals. Recently it was shown that the Darwinian mechanism can be viewed as a form of machine learning, the field of computer science that studies systems in which most of the information is acquired from experience and not from a programmer. The goal of the research is to understand what classes of functions, such as those occurring in protein expression networks, can so evolve using practicable resources. Graduate students will be involved in these projects.

计算复杂性是研究执行计算任务需要多少资源的领域。它的主要重点是了解在传统计算机上执行各种重要任务需要多少步骤和多少存储空间。生物过程也可以被视为计算，因为它们由遵循某些规则的逐步过程组成，并且也可以从计算复杂性理论的角度进行研究。这项建议涉及研究这两个方面。它的目标是证明，通过数学手段，上限或下限的通用和进化计算所需的资源。虽然很多了解的复杂性计算的通用计算机上，这种理解是围绕少数关键的开放问题，如P=？NP问题，其答案将解决许多重要任务的资源需求。本研究的第一个重点将是这些问题的代数方法，其中代数公理对计算的限制进行了分析。全息算法在过去的十年中产生了新的算法的各种问题，以及新的下限参数，也证明计算等价性之间的新技术显然不同的问题。这项研究的目标是了解全息算法的固有限制，并利用这种理解来开发有效的算法。达尔文进化论也可以被看作是一个计算过程，使用可量化的资源，在这里衡量的代数，人口规模和个人的经验数量。最近有研究表明，达尔文机制可以被视为机器学习的一种形式，机器学习是计算机科学的一个领域，研究的系统中，大部分信息是从经验中获得的，而不是从程序员那里获得的。这项研究的目标是了解哪些功能类别，例如蛋白质表达网络中的功能，可以使用可行的资源进行进化。 研究生将参与这些项目。