6
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ Not closed under what operation? For example, the class of recursively enumerable languages has complete problems (e.g. the halting problem), but is not closed under complement. $\endgroup$ – Huck Bennett Mar 18 '12 at 17:55
14
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.