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.