  We consider the algorithmic problem of finding a near ground state (near
optimal solution) of a $p$-spin model. We show that for a class of algorithms
broadly defined as Approximate Message Passing (AMP), the presence of the
Overlap Gap Property (OGP), appropriately defined, is a barrier. We conjecture
that when $p\ge 4$ the model does indeed exhibits OGP (and prove it for the
space of binary solutions). Assuming the validity of this conjecture, as an
implication, the AMP fails to find near ground states in these models, per our
result. We extend our result to the problem of finding pure states by means of
Thouless, Anderson and Palmer (TAP) based iterations, which is yet another
example of AMP type algorithms. We show that such iterations fail to find pure
states approximately, subject to the conjecture that the space of pure states
exhibits the OGP, appropriately stated, when $p\ge 4$.
