On Datalog vs. polynomial time

Abstract

We show that certain monotonie polynomial time queries are not expressible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a "Pumping Lemma" for Datalog queries.