  In this paper we investigate the entanglement properties of the class of
$\pi$-locally maximally entanglable ($\pi$-LME) states, which are also known as
the "real equally weighted states" or the "hypergraph states". The $\pi$-LME
states comprise well-studied classes of quantum states (e.g. graph states) and
exhibit a large degree of symmetry. Motivated by the structure of LME states,
we show that the capacity to (efficiently) determine if a $\pi$-LME state is
entangled would imply an efficient solution to the boolean satisfiability (SAT)
problem. More concretely, we show that this particular problem of entanglement
detection, phrased as a decision problem, is $\mathsf{NP}$-complete. The
restricted setting we consider yields a technically uninvolved proof, and
illustrates that entanglement detection, even when quantum states under
consideration are highly restricted, still remains difficult.
