Computing the Mobius function The Mobius function $\mu(n)$ is defined as $\mu(1)=1$, $\mu(n)=0$ if $n$ has a squared prime factor, and $\mu(p_1 \dots p_k)= (-1)^k$ if all the primes $p_1,\dots,p_k$ are different. Is it possible to compute $\mu(n)$ without computing the prime factorization of $n$?
One non-answer to your question is that SQUARE-FREE (is a number square free) is itself not known to be in P, and computing the Möbius function would solve this problem (since a square free number has $\mu(n) \neq 0$).