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 问题的答案。本研究的第一个重点将是解决这些问题的代数方法，其中分析了代数公理对计算的限制，在过去的十年中产生了新颖的算法。对于各种问题，以及新的下界参数，以及证明明显不同的问题之间的计算等价性的新技术，该研究的目标是了解全息算法的固有局限性，并利用这种理解来开发有效的算法。达尔文进化论也可以被视为一种使用可量化资源的计算过程，这里以世代数量、人口规模和个体经验数量来衡量。最近的研究表明，达尔文机制可以被视为一种形式。机器学习，计算机科学领域研究的系统中大部分信息都是从经验中获得的，而不是从程序员那里获得的。该研究的目标是了解哪些类别的功能（例如蛋白质表达网络中出现的功能）可以使用实用的资源进行进化。将参与这些项目。