Entanglement, intractability and no-signaling