Aspects of Computation Theory

点击翻译按钮获取中文摘要

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.