"In three dimensions, the problem is NP-complete even for two nested convex polyhedra":

Mitchell, Joseph SB, and Subhash Suri. "Separation and approximation of polyhedral objects." Computational Geometry 5, no. 2 (1995): 95-114. doi.

"In three dimensions, we show how to separate a convex polyhedron from a nonconvex polyhedron with a polyhedral surface whose facet-complexity is $O(\log n)$ times the optimal, where $n=|P|+|Q|$ is the complexity of the input polyhedra. Our algorithm runs in $O(n^4)$ time, but improves to $O(n^3)$ time if the two polyhedra are nested and convex."

"In three dimensions, the problem is NP-complete even for two nested convex polyhedra":

Mitchell, Joseph SB, and Subhash Suri. "Separation and approximation of polyhedral objects." Computational Geometry 5, no. 2 (1995): 95-114. doi.

"In three dimensions, we show how to separate a convex polyhedron from a nonconvex polyhedron with a polyhedral surface whose facet-complexity is $O(\log n)$ times the optimal, where $n=|P|+|Q|$ is the complexity of the input polyhedra. Our algorithm runs in $O(n^4)$ time, but improves to $O(n^3)$ time if the two polyhedra are nested and convex."

The $O(\log n)$ factor derives from approximating the set cover problem.