The complexity of LSH feasibility