Les grands graphes aléatoires sont-ils toujours sûrs pour se cacher ?

Nous discutons des possibilités de victoire des joueurs dans diverses variantes du jeu des policiers et des voleurs joué sur de grands graphes aléatoires, un banc d'essai pour divers types de requêtes réseau, en particulier des problèmes de recherche. Nous explorons l'utilisation de cadres logiques pour enquêter sur de tels résultats ; en particulier, nous montrons que chaque fois qu'une condition de victoire pour un joueur peut être exprimée comme un certain type de formule en logique du premier ordre, ce joueur gagne presque toujours. Dans ce processus, nous obtenons plus de compréhension sur la connexion logique-jeu du point de vue de la loi zéro-un.