Aspects of Computation Theory

这是一个研究计算理论各个领域的项目， 包括复杂性理论、逻辑编程和常识 推理 PI正在继续研究NP的0-1定律 问题，研究的渐近概率的调查 NP问题，并确定计算这些问题的复杂性 概率 也有工作在寻找之间的联系 NP问题的逻辑可定义性和平均情况复杂性。 的 PI正在研究逻辑查询程序的并行复杂性， 将尝试开发建立下限类型的方法 数据库查询语言的表达能力。 最后，讨论了在研究中出现的一些计算问题。 限制和其他相关领域的常识推理 正在被探索。

This is project for research in various areas of computation theory, including complexity theory, logic programming, and common-sense reasoning. The PI is continuing the investigation of 0-1 laws for NP problems, an investigation that studies the asymptotic probabilities of NP problems and identifies the complexity of computing these probabilities. There is also work on finding connections between logical definability and average case complexity of NP problems. The PI is studying the parallel complexity of logical query programs and shall attempt to develop methods for establishing lower bound type results about the expressive power of database query languages. Finally, some computational issues arising in the study of circumscription and in other related areas of common-sense reasoning are being explored.