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.