Are there non-closed complexity classes for which there are complete problems?

Question

Is saying that a class is non closed analogous to stating there are complete problems that have not been identified for that class under a certain type of reduction?

Answer 1

I assume that you are asking about the relation between a complexity class having a complete problem under a certain notion of reducibility and the same complexity class being closed under the same notion of reducibility. It is a common misunderstanding that these two notions are related. They are not!

For example, SAT is an NP-complete problem under polynomial-time Turing reducibility. But NP is not closed under polynomial-time Turing reducibility unless, say, NP=coNP. On the other hand, PH is closed under polynomial-time Turing reducibility, but PH does not have a complete problem unless the polynomial hierarchy collapses to a finite level.

This is not to say that complete problems and the closure property are unrelated. For example, consider the equivalence that P=NP if and only if SAT∈P. One explanation for this equivalence is that it holds because SAT is NP-complete under polynomial-time Turing reducibility and P (not NP!) is closed under the same notion of reducibility. Of course, this is a little contrived explanation for this equivalence because we do not have to use Turing reducibility and we can use many-one reducibility instead, under which both P and NP are closed. But when we consider classes of relation problems such as FP and FNP and consider polynomial-time function reducibility, then we have to be careful about which class is closed and which class is not, because FNP is not necessarily closed under polynomial-time function reducibility. Still, the notion of FNP-complete problems is useful because FP is closed under polynomial-time function reducibility.