Ehrenfeucht-Fraiesse Games on Random Structures

摘要

Certain results in circuit complexity (e.g., the theorem that AC~0 functions have low average sensitivity [5, 17]) imply the existence of winning strategies in Ehrenfeucht-Fraiesse games on pairs of random structures (e.g., ordered random graphs G = G(n, 1/2) and G~+ = G ∪ {random edge}). Standard probabilistic methods in circuit complexity (e.g., the Switching Lemma [11] or Razborov-Smolensky Method [19, 21]), however, give no information about how a winning strategy might look. In this paper, we attempt to identify specific winning strategies in these games (as explicitly as possible). For random structures G and G~+, we prove that the composition of minimal strategies in r-round Ehrenfeucht-Fraiesse games partial deriv_r(G,G) and partial deriv_r(G~+ ,G~+) is almost surely a winning strategy in the game partial deriv_r(G, G~+). We also examine a result of [20] that ordered random graphs H = G(n, p) and H~+ = H ∪ {random fc-clique} with p(n) n~((-2)/(k-1)) (below the k-clique threshold) are almost surely indistinguishable by [k/4] -variable first-order sentences of any fixed quantifier-rank r. We describe a winning strategy in the corresponding r-round [k/4]-pebble game using a technique that combines strategies from several auxiliary games.