Ebbing, Johannes and Kontinen, Juha and Müller, Julian-Steffen and Vollmer, Heribert - A Fragment of Dependence Logic Capturing Polynomial Time

lmcs:795 - Logical Methods in Computer Science, August 15, 2014, Volume 10, Issue 3
A Fragment of Dependence Logic Capturing Polynomial Time

Authors: Ebbing, Johannes and Kontinen, Juha and Müller, Julian-Steffen and Vollmer, Heribert

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 study the question which of our results can ge generalized to the case of open formulae of D-Horn* and so-called downwards monotone polynomial time properties of teams.


Source : oai:arXiv.org:1210.3321
DOI : 10.2168/LMCS-10(3:3)2014
Volume: Volume 10, Issue 3
Published on: August 15, 2014
Submitted on: September 12, 2013
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity


Share

Consultation statistics

This page has been seen 71 times.
This article's PDF has been downloaded 24 times.