On Datalog vs Polynomial Time

摘要

We show that certain monotonic 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.