  Does gravity constrain computation? We study this question using the AdS/CFT
correspondence, where computation in the presence of gravity can be related to
non-gravitational physics in the boundary theory. In AdS/CFT, computations
which happen locally in the bulk are implemented in a particular non-local form
in the boundary, which in general requires distributed entanglement. In more
detail, we recall that for a large class of bulk subregions the area of a
surface called the ridge is equal to the mutual information available in the
boundary to perform the computation non-locally. We then argue the complexity
of the local operation controls the amount of entanglement needed to implement
it non-locally, and in particular complexity and entanglement cost are related
by a polynomial. If this relationship holds, gravity constrains the complexity
of operations within these regions to be polynomial in the area of the ridge.
