Foundational Issues in Computer Science

该项目调查了三个不同的领域。 (1)平均案件复杂度。 主要目标是使人们能够证明现实生活中的决策和搜索问题的平均情况下的硬度。 研究涉及到重新审视平均情况约简和平均情况多项式时间的基本定义。 (2)有限模型理论 最具挑战性的问题是是否存在一种逻辑，可以在任意（不一定是有序的）结构上捕获多项式时间的概念。 几年前，PI推测答案是否定的。 研究的重点是多项式时间的哪些部分可以被逻辑捕获。 另一个方向是将有限模型理论的方法扩展到研究无限域中带权的有限结构。 (3)抽象状态机。 抽象状态机是一种新的计算模型，它已被成功地用于描述和验证现实生活中的算法。 在这里，该模型被应用到复杂性理论和有限模型理论。

This project investigates three distinct areas. (1) Average case complexity. The major goal is to enable one to prove the average case hardness of real-life decision and search problems. The research involves reexaming the basic definition of average-case reduction and average-case polynomial-time. (2) Finite model theory. The most challenging question is whether there exists a logic that captures the notion of polynomial-time on arbitrary (not necessarily ordered) structures. The PI has conjecture a few year ago that the answer is negative. The thrust of the research is the question what parts of polynomial time can be captured by logics. Another direction is extension of the methods of finite model theory to the study of finite structures with weights in infinite domains. (3) Abstract state machines. Abstract state machines is a new model of computation which has been successfully used to specify and verify real-life algorithms. Here this model is applied to complexity theory and finite model theory.