Abstract: Does gravity constrain computation? We study this question usingthe AdS/CFT correspondence, where computation in the presence ofgravity can be related to non-gravitational physics in the boundary theory. In AdS/CFT, computations which happen locally in the bulk areimplemented in a particular non-local form in the boundary, which ingeneral requires distributed entanglement. In more detail, we recall thatfor a large class of bulk subregions the area of a surface called the ridgeis equal to the mutual information available in the boundary to performthe computation non-locally. We then argue the complexity of the localoperation controls the amount of entanglement needed to implement itnon-locally, and in particular complexity and entanglement cost are related by a polynomial. If this relationship holds, gravity constrains thecomplexity of operations within these regions to be polynomial in thearea of the ridge.