  We perform a mathematical analysis of the classical computational complexity
of two genuine quantum-mechanical problems, which are inspired in the
calculation of the expected magnetizations and the entanglement between
subsystems for a quantum spin system. These problems, which we respectively
call SES and SESSP, are specified in terms of pure slightly-entangled quantum
states of n qubits, and rigorous mathematical proofs that they belong to the
NP-Complete complexity class are presented. Both SES and SESSP are, therefore,
computationally equivalent to the relevant 3-SAT problem, for which an
efficient algorithm is yet to be discovered.
