The Intractability of the Nonidentity Problem