  In view of the importance of quantum non-locality in cryptography, quantum
computation and communication complexity, it is crucial to decide whether a
given correlation exhibits non-locality or not. In the light of a theorem by
Pitowski, it is generally believed that this problem is computationally
intractable. In this paper, we first prove that the Euclidean distance of given
correlations from the local polytope can be computed in polynomial time with
arbitrary fixed error, granted the access to a certain oracle. Namely, given a
fixed error, we derive two upper bounds on the running time. The first bound is
linear in the number of measurements. The second bound scales as the number of
measurements to the sixth power. The former is dominant only for a very high
number of measurements and is never saturated in the performed numerical tests.
We then introduce a simple algorithm for simulating the oracle. In all the
considered numerical tests, the simulation of the oracle contributes with a
multiplicative factor to the overall running time and, thus, does not affect
the sixth-power law of the oracle-assisted algorithm.
