The problem is NP hard. Here is a proof sketch.

The problem is to determine if there is a point $y$ with $\|y\|=1$ outside of the convex hull of given points $x_1,\dots, x_n$. Note that such point exists if and only if there is hyperplane at distance less than $1$ from the origin such that all points $x_1, \dots, x_n$ and $0$ lie on one side of the hyperplane (consider a hyperplane $\pi$ separating $x_1,\dots, x_n, 0$ and $y$).

So the problem can be stated as follows: is there $a\in {\mathbb R}^d$ s.t.

- $\langle a, x_i\rangle \leq 1$ (that is, all $x_i$ lie in the half-space $\{x: \langle a, x\rangle\leq 1\}$);
- $\|a\| > 1$.

Note that this problem is equivalent to the following well-known problem:

We are given a convex polytope $\cal P$, a positive definite matrix $A$ and a number $t$, find $x\in \cal P$ such that $x^T A x > t$. ($\cal P$ is described by a system of linear equations).

The optimization version of this problem is:

**Quadratic Programming (Non-convex Linearly Constrained Quadratic Programming with Positive Definite Matrix).** We are given a convex polytope $\cal P$ and and a positive definite matrix $A$, find $x\in \cal P$ that maximizes $x^T A x$.

This problem is known to be NP hard.

It is even NP-hard to optimize $x^T A x$ when $\cal P$ is the unit cube $\{(b_1, \dots, b_d): -1\leq b_i \leq 1\}$ (this problem is known as *Integer Quadratic Programming with Positive Definite Matrix*). In particular, the MAX CUT problem is a special case of this problem. Let $G$ be a graph on $n$ vertices and $L$ be its Laplacian. Then $\max_{x\in\{\pm 1\}^n} x^T L x$ is equal to the size of the maximum cut in $G$ ($L$ is positive *semi*-definite, not positive definite, but this difference is not important; e.g. we can consider $L'=L+\varepsilon I$ with very small $\varepsilon$). The NP-hardness of MAX CUT was proved by Karp in

*Richard M. Karp (1972). Reducibility Among Combinatorial Problems. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.*

1more comment