# The characterization of a problem as PSPACE-complete is …?

Let's assume that you found out that some problem $$\mathit{\Pi}$$ is PSPACE-complete (with respect to your favorite kind of reductions, say, logspace reductions). However, as there are dozens of well-known and very different PSPACE-complete problems, this characterization doesn't tell you much about the real hardness of deciding membership in $$\mathit{\Pi}$$ (and you determine to refine the hardness of membership in $$\mathit{\Pi}$$ further by some other means, i.e., different from the good old standard complexity classes). Now, how do you express in plain English the unsatisfactory fact that the PSPACE-completeness of $$\mathit{\Pi}$$ doesn't tell you too much? Do you say that the PSPACE-completeness characterization of $$\mathit{\Pi}$$ is

• coarse

• coarse-grained

• coarsely grained

• coarsely granular

• crude

• gross

• grainy

• granular

• rough

• unrefined

• ... (your choice goes here) ...

?

Which word is idiomatic?

## 1 Answer

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.

• In the same vein as "unenlightening" and "unilluminating", I was about to suggest "uninformative" or "insufficiently informative". – mhum Feb 28 at 0:40