How does one determine if a mixed bipartite quantum state is entangled or not?
In http://arxiv.org/pdf/quant-ph/0303055v1.pdf, it is shown that the weak membership problem for the set of separable states is NP-hard. As you can see in Definition 6.2 (page 18), this amounts to deciding if a state has a separable decomposition up to accuracy $\delta$.

If you want to convert this to a search problem, you can thus do so by using a $\delta$-net on the set of all separable decompositions and doing an exhaustive search.  Note that the maximal number of terms required in such a decomposition is bounded by $(d_Ad_B)^2$ (where $d_A$ and $d_B$ are the dimensions of the two systems). 

In particular, such a decomposition to accuracy $\delta$ can be used as a proof for weak membership in the set of separable states, proving that the problem is in NP.

Note that the problem clearly remains NP-hard for any higher accuracy (i.e. any accuracy which increases with the problem size).  On the other hand, since any separable decomposition with $N$ digits of accuracy can be verified in $\mathrm{poly}(N)$ time, the problem remains inside NP (and thus NP-complete) even with an exponential precision.