Name
Abstract | ||
|---|---|---|
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 easily be determined in polynomial time, where the degree of the polynomial is linear in k. We show that this linear dependence on the parameter k is necessary by proving an unconditional polynomial lower bound for determining the winner in the existential k-pebble game on finite structures. Establishing strong k-consistency is a well-known heuristic for solving the constraint satisfaction problem (CSP). By the game characterization of Kolaitis and Vardi our result implies a lower bound on every algorithm that decides if strong k-consistency can be established for a given CSP-instance. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/LICS.2012.14 | Logical Methods in Computer Science |
Keywords | DocType | Volume |
k-consistency tests,constraint satisfaction problem,polynomial time,existential-positive k-variable fragment,existential pebble games,parameter k,strong k-consistency,existential k-pebble game,lower bounds,game characterization,linear dependence,unconditional polynomial,finite structure,computational complexity,formal logic,computer science,polynomials,constraint satisfaction problems,games,switches,indexes,game theory,first order logic,color | Conference | 9 |
Issue | ISSN | Citations |
4 | Logical Methods in Computer Science, Volume 9, Issue 4 (October 8,
2013) lmcs:1010 | 3 |
PageRank | References | Authors |
0.40 | 9 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Berkholz | 1 | 49 | 7.03 |