AF: Medium: Algorithmic Complexity in Computation and Biology

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

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.