LOWER BOUNDS FOR EXISTENTIAL PEBBLE GAMES AND k-CONSISTENCY TESTS

作     者：Berkholz, Christoph 

作者机构：Rhein Westfal TH Aachen Lehrstuhl Informat 7 Aachen Germany 

出 版 物：《LOGICAL METHODS IN COMPUTER SCIENCE》 (Log. Methods Comp. Sci.)

年 卷 期：2013年第9卷第4期

核心收录：

学科分类：08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：existential pebble game finite variable logic first order logic parameterized complexity theory k-consistency constraint propagation 

摘      要：The existential k-pebble game characterizes the expressive power of the existential- positive k-variable fragment of first-order logic on finite structures. The winner of the existential k-pebble game on two given finite structures can be determined in time O(n(2k)) by dynamic programming on the graph of game configurations. We show that there is no O(n((k-3)/12))-time algorithm that decides which player can win the existential k-pebble game on two given structures. This lower bound is unconditional and does not rely on any complexity-theoretic assumptions. Establishing strong k-consistency is a well-known heuristic for solving the constraint satisfaction problem (CSP). By the game characterization of Kolaitis and Vardi [14] our result implies that there is no O(n((k-3)/12))-time algorithm that decides if strong k-consistency can be established for a given CSP-instance.