Lower bounds on the complexity of model-checking

详细信息    查看全文

• 作者：Robert Ganian ; Petr Hlin¨§ny ; Alex ; er Langer ; Jan Obdr?¨¢lek ; Peter Rossmanith ; Somnath Sikdar
• 关键词：Graph MSO logic ; Tree-width ; Digraph width ; Intractability
• 刊名：Journal of Computer and System Sciences
• 出版年：2014
• 出版时间：February, 2014
• 年：2014
• 卷：80
• 期：1
• 页码：180-194
• 全文大小：436 K

文摘

Kreutzer and Tazari proved in 2010 that model-checking is not polynomial (XP) w.r.t. the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. We prove that model-checking with a fixed set of vertex labels ¡ª i.e., without edge-set quantification ¡ª is not solvable even in quasi-polynomial time for fixed -formulas in such graph classes. Both the lower bounds hold modulo a certain complexity-theoretic assumption, namely, the Exponential-Time Hypothesis (ETH) in the former case and the non-uniform ETH in the latter case. In comparison to Kreutzer and Tazari, we show a different set of problems to be intractable, and our stronger complexity assumption of non-uniform ETH slightly weakens assumptions on the graph class and greatly simplifies important lengthy parts of the former proof. Our result also has an interesting consequence in the realm of digraph width measures.