Complexity results for dependence logic
Seminar Room 1, Newton Institute
Dependence Logic, introduced by Jouko Väänänen in 2007, is a new logic incorporating the concept of dependence into first-order logic. The expressive power of dependence logic coincides with that of existential second-order logic, and the complexity class NP over finite structures. In the past few years, dependence logic has grown into a new framework in which various notions of dependence and independence can be formalized. We review
recent results regarding the expressive power and complexity of certain fragments and extensions of dependence logic.