A fragment of dependence logic capturing polynomial time

Abstract

In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we define an even smaller fragment D*-Horn and show that over finite successor structures it captures the complexity class P of all sets decidable in polynomial time. Furthermore, we show that the open D*-Horn-formulae correspond to the negative fragment of SO there exists-Horn.