Consider this problem:
PROBLEM: Given a positive integer $n > 1$. Question. Is $n$ the sum of two squares?
Actually there are three levels to the problem. The above is Level 1. The Level 2 Question is "Express $n$ as a sum of two squares". Level 3's Question is "Write down all ways in which $n$ is the sum of two squares".
I note that if one had an oracle that could factor numbers instantly, then all three of these problems can be solved in polynomial time. This means these problems are no harder than the Factorization Problem (FP)(Given n. Question: write down the factorization into primes of $n$). FP is in both NP and co-NP, so these problems are probably not NP-complete. What I am wondering is if any of these three problems is easier than FP, or maybe even polynomial (in P). If $n$ has a factor of the form $(4k-1)^p$ where $p$ is odd, then one can answer right away, "No" to all three problems. The problem comes with a number of the form $n$ = $4k+1$ for some positive $k$. Does it have factors of the form $4q-1$ or not? Can this be obtained somehow without having to factor $n$? Right now I can't think of a way.