Aspects of Computation Theory and Logic

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

The principal investigator works on a broad spectrum of problems in finite model theory, which is the subject that studies first-order logic and its extensions on collections of finite structures. He seeks to discover necessary and sufficient conditions under which logics with fixpoint operators capture computational complexity classes on collections of finite structures. Moreover , he investigates the comparative expressive power of extensions of first-order logic on collections as finite structures of asymptotic measure equal to one. He also studies various aspects of logics with fixed finite number of variables, including algorithms for satisfiability, and asymptotic probabilities of properties expressible in such logics. Progress on these problems will strengthen the connections between logic and computation, and enhance the interaction between logic, computational complexity, and asymptotic combinatorics. In a different direction, He continues working towards the development of a structural approximation theory for combinatorial optimization within the framework of integer programming. The objective of this investigation is to identify large classes of NP optimization problems possesing approximation algorithms with performance guarantees.***