Computational complexity and logic

计算复杂性和逻辑

• 批准号: 7755-2011
• 负责人: Cook, Stephen
• 金额: $ 6.99万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568535
• 关键词: Computational; complexity; logic

I plan on continuing my research in both computational complexity and proof complexity. My current work in complexity theory is motivated by the problem of separating logarithmic space (deterministic and nondeterministic) from polynomial time. My collaborators and I have formulated a computational problem (the Tree Evaluation Problem), for which we have a conjectured space-optimal algorithm requiring superlogarithmic space. We use the branching program model of computational space, for which a superpolynomial lower bound on the number of states implies the desired separation. We have proved such a lower bound for restricted branching programs, and will work toward gradually removing the restrictions. In proof complexity I will continue working with my students on projects motivated by understanding the complexity of concepts needed to prove combinatorial theorems.

我计划继续我在计算复杂性和证明复杂性方面的研究。 我目前在复杂性理论方面的工作是由从多项式时间中分离对数空间（确定性和非确定性）的问题激发的。 我的合作者和我已经制定了一个计算问题（树评估问题），对于这个问题，我们有一个需要超对数空间的约束空间最优算法。 我们使用分支程序模型的计算空间，其中一个超多项式下界的状态数意味着所需的分离。 我们已经证明了这样一个限制分支程序的下界，并将逐步消除限制。 在证明复杂性，我将继续与我的学生在项目的动机理解所需的概念证明组合定理的复杂性。