
Existential kpebble games, where k is a positive integer, are combinatorial games played between two players, called the Spoiler and the Duplicator, on two structures. These games were originally introduced in order to analyze the expressive power of Datalog and related infinitary logics with finitely many variables. More recently, however, it was realized that existential kpebble games have tight connections with certain consistency properties which play an important role in identifying tractable classes of constraint satisfaction problems and in designing heuristic algorithms for solving such problems. Specifically, it has been shown that strong kconsistency can be established for an instance of constraint satisfaction if and only if the Duplicator has a winnning strategy for the existential kpebble game between two finite structures associated with the given instance of constraint satisfaction.
In this paper, we pinpoint the computational complexity of determining the winner of the existential kpebble game. The main result is that the following decision problem is EXPTIMEcomplete: given a positive integer k and two finite structures A and B, does the Duplicator win the existential kpebble game on A and B? Thus, all algorithms for determining whether strong kconsistency can be established (when k is part of the input) are inherently exponential.
© 20022003 Kurt Gödel Society, Norbert Preining. 
20030604
 