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.