  Computing the ground state of Ising spin-glass models with p-spin
interactions is, in general, an NP-hard problem. In this work we show that
unlike in the case of the standard Ising spin glass with two-spin interactions,
computing ground states with p=3 is an NP-hard problem even in two space
dimensions. Furthermore, we present generic exact and heuristic algorithms for
finding ground states of p-spin models with high confidence for systems of up
to several thousand spins.
