What is the Complexity of a Random Map?

A class of structures obeys a 0-1 law if every first-order sentence has an asymptotic probability of 0 or 1 within the class. Techniques used to prove 0-1 laws are closely related to average-case analyses of algorithms. For example, Abiteboul, Compton and Vianu showed that the 0-1 law for random relational structures (which includes random graphs with constant edge probabilities) can be used to give an average-case analysis of certain database query optimizations. However, the random graph model is not a very realistic model for databases, so it is useful to examine other structures. A map, or embedding of a graph into a surface of fixed genus, may be a better model of certain kinds of geometric databases. Bender, Compton, and Richmond showed that the class of random maps in surface of fixed genus obeys a 0-1 law. We will analyze the complexity of the problem of deciding whether a given sentence has a probability of 1, and argue that it is unlikely that query optimization algorithms will give significant improvements on random maps.