  We shed new light on entanglement measures in multipartite quantum systems by
taking a computational-complexity approach toward quantifying quantum
entanglement with two familiar notions--approximability and distinguishability.
Built upon the formal treatment of partial separability, we measure the
complexity of an entangled quantum state by determining (i) how hard to
approximate it from a fixed classical state and (ii) how hard to distinguish it
from all partially separable states. We further consider the
Kolmogorovian-style descriptive complexity of approximation and distinction of
partial entanglement.
