  According to the AdS/CFT correspondence, the geometries of certain spacetimes
are fully determined by quantum states that live on their boundaries -- indeed,
by the von Neumann entropies of portions of those boundary states. This work
investigates to what extent the geometries can be reconstructed from the
entropies in polynomial time. Bouland, Fefferman, and Vazirani (2019) argued
that the AdS/CFT map can be exponentially complex if one wants to reconstruct
regions such as the interiors of black holes. Our main result provides a sort
of converse: we show that, in the special case of a single 1D boundary, if the
input data consists of a list of entropies of contiguous boundary regions, and
if the entropies satisfy a single inequality called Strong Subadditivity, then
we can construct a graph model for the bulk in linear time. Moreover, the bulk
graph is planar, it has $O(N^2)$ vertices (the information-theoretic minimum),
and it's ``universal,'' with only the edge weights depending on the specific
entropies in question. From a combinatorial perspective, our problem boils down
to an ``inverse'' of the famous min-cut problem: rather than being given a
graph and asked to find a min-cut, here we're given the values of min-cuts
separating various sets of vertices, and need to find a weighted undirected
graph consistent with those values. Our solution to this problem relies on the
notion of a ``bulkless'' graph, which might be of independent interest for
AdS/CFT. We also make initial progress on the case of multiple 1D boundaries --
where the boundaries could be connected via wormholes -- including an upper
bound of $O(N^4)$ vertices whenever a planar bulk graph exists (thus putting
the problem into the complexity class $\mathsf{NP}$).

Quantum Physics;Computational Complexity;General Relativity and Quantum Cosmology;High Energy Physics - Theory