A Query regarding Quadratic Residuocity Problem
It can be solved in randomized polynomial time, so it's not NP-complete (unless RP=NP, which is considered unlikely).

If $n=p_1p_2p_3$ is composite, where $p_1,p_2,p_3$ are three distinct prime factors, and $p_1,p_2,p_3$ are given, then the problem can be solved in polynomial time.  In particular, in this case, there are only 8 square roots of $q$ (modulo $n$), and you can enumerate them all and check whether any of them are in the range $[0,c)$.

Details and justification: you can use the Chinese remainder theorem.  Let $x_1$ be one of the two square roots of $q$ modulo $p_1$, i.e., it satisfies $x_1^2 \equiv q \pmod{p_1}$.  (Then the other square root is $-x_1$.)  Similarly, let $x_2$ be a square root modulo $p_2$ and $x_3$ a square root modulo $p_3$.  Then you can find a square root modulo $n$ by using the Chinese remainder theorem to find the unique solution to $x \equiv x_1 \pmod{p_1}$, $x \equiv x_2 \pmod{p_2}$, $x \equiv x_3 \pmod{p_3}$.  In general, you can look for $x$ to be $x_1$ or $-x_1$ mod $p_1$, and $x_2$ or $-x_2$ mod $p_2$, and $x_3$ or $-x_3$ mod $p_3$; each of those $2 \times 2 \times 2 = 8$ combinations gives a different square root of $q$ modulo $n$.  You can find $x_1,x_2,x_3$ in randomized polynomial time, and the CRT computation can be done in polynomial time, so you can enumerate all square roots modulo $n$ in polynomial time.

This same argument generalizes to any case where the number of prime factors of $n$ is constant, and where those prime factors are given in advance.  However, when the number of prime factors is unlimited, this line of argument doesn't work, so this won't work for general $n$.