<p>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!</p>

<p>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, <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#ph">PH</a> is closed under polynomial-time Turing reducibility, but PH does not have a complete problem unless the polynomial hierarchy collapses to a finite level.</p>

<p>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 <em>P (not NP!) is closed under the same notion of reducibility</em>.  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 <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#fp">FP</a> and <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#fnp">FNP</a> 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.</p>

CC BY-SA 3.0
2012-03-18T18:27:02.137Z
2012-03-18T18:42:20.560Z
2012-03-18T18:42:20.560Z
Tsuyoshi Ito
<p>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?</p>

CC BY-SA 3.0
2012-03-18T17:55:45.047Z
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.
Huck Bennett
<cc.complexity-theory><complexity-classes><reductions>
Are there non-closed complexity classes for which there are complete problems?
user375334
# Are there non-closed complexity classes for which there are complete problems?

(Asked by: username_0 on 2012-03-18)

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?

**Tags:** cc.complexity-theory, complexity-classes, reductions
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2012-03-18. Score: 14 | Accepted answer

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](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#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](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#fp) and [FNP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#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.


---

