Finitely Bounded Homogeneity Turned Inside-Out

The classification problem for countable finitely bounded homogeneous structures is notoriously difficult, with only a handful of published partial classification results, e.g., for directed graphs. We prove the Inside-Out correspondence, which states that the classification problem, viewed as a computational decision problem, is polynomial-time equivalent to the problem of testing the containment between finitely bounded amalgamation classes up to taking reducts to a given subset of their signatures. The correspondence enables polynomial-time reductions from various decision problems that can be represented within such containment, e.g., the double-exponential square tiling problem. This leads to a new lower bound for the complexity of the classification problem: $\textsf{2NEXPTIME}$-hardness. On the other hand, it also follows from the correspondence that the classification (decision) problem is effectively reducible to the (search) problem of finding a finitely bounded Ramsey expansion of a finitely bounded strong amalgamation class. We subsequently prove that the closely related problem of homogenizability is already undecidable.