文章基本信息

标题：An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity
本地全文：下载
作者：Benjamin Rossman
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：67
页码：27:1-27:17
DOI：10.4230/LIPIcs.ITCS.2017.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Previous work of the author [Rossmann'08] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC0 formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence of quantifier-rank k is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence of quantifier-rank poly(k). Quantitatively, this improves the result of [Rossmann'08], where the upper bound on quantifier-rank is a non-elementary function of k.
关键词：circuit complexity; finite model theory