The characterization of a problem as PSPACE-complete is ...?
Several are idiomatic: "coarse", "coarse-grained", "crude", "rough", "unrefined". These all (roughly) mean 'lacking in [fine] detail'.

"Coarsely grained" and "coarsely granular" don't work well in this case (though the meaning would not be lost, it just reads strangely). These two imply that you're talking about properties of the object (in this case the characterisation - the first that it has a grain of some kind which is coarse, the second that it comes in rough lumps).

"Gross", "grainy" and "granular" don't work at all, and would require the reader to guess that you actually meant to write something else. The "grain" in "coarse-grained" refers to meaning 5, not meaning 1 as described here, so the adjective granular is incorrect. "gross" at its root means "large", so doesn't give the right intent here either.

As an alternative with a different core meaning, you could say that it's "unenlightening", or "unilluminating", suggesting that it doesn't tell you much, rather than it's rough.