<p>I'm not entirely clear on your notation, but if you define a complexity class as the closure of a particular problem under PTIME reductions, then it will of course be closed under PTIME reductions. </p>

<p>On the other side, you can easily create a class $A$ that isn't closed under PTIME reductions, a trivial example would be to just pick a class that contains one $NP$-complete problem (say $A = \{SAT\}$). Is this what you mean?</p>

<p>A third point is that you can have classes that are closed, but have no complete problems - the Polynomial Hierarchy has no complete problems unless it collapses to finitely many levels (which seems unlikely).</p>

CC BY-SA 3.0
2012-08-01T14:50:01.090Z
@Geekster: why not? All three things he has stated are pretty clearly correct. Any class defined as the **PTIME** closure of a problem will be **PTIME** closed; no single problem is **PTIME** closed; and his statement about **PH** is also correct. What specifically do you think is wrong?
Niel de Beaudrap
CC BY-SA 3.0
2012-08-01T15:13:03.323Z
@NieldeBeaudrap NP is not closed under any polynomial time reduction? How about CoNP? C=P or PP?
Tayfun Pay
CC BY-SA 3.0
2012-08-01T15:26:38.960Z
@Geekster: a singleton-set *S* consisting of any *single* **NP**-complete problem is not closed under **PTIME** reduction. After all, the closure of *S*  under **PTIME** reduction is **NP**, by definition, which contains more problems than *S* does.
Niel de Beaudrap
CC BY-SA 3.0
2012-08-01T15:32:31.990Z
But does {SAT} really qualify as a _complexity class_?
Jeffε
CC BY-SA 3.0
2012-08-01T15:43:37.603Z
@JɛﬀE: it certainly isn't a very natural one, but is the lack of naturalness the only complaint? Would the situation be much improved if we took the closure of {SAT} under logarithmic-time reductions?
Niel de Beaudrap
CC BY-SA 3.0
2012-08-01T15:57:36.157Z
Guys I am not asking about this... Then I can go to any question, interpret it the way I want to and answer it...
Tayfun Pay
CC BY-SA 3.0
2012-08-01T20:05:24.587Z
@Geekster, the problem is that your question is vague. Luke's interpretation is consistent with what you have written. If this is not what you intended to ask then your question allows multiple interpretations. People cannot guess what is your intention, it is your responsibility to write questions in a clear way that is unambiguous and does not lead to multiple interpretations.
Kaveh
CC BY-SA 3.0
2012-08-01T20:08:18.247Z
@JɛﬀE, do you know a definition of "complexity class" (of decision problems) other than a set of subsets of $\Sigma^*$?
Kaveh
CC BY-SA 3.0
2012-08-01T12:01:48.173Z
2012-08-01T12:01:48.173Z
Luke Mathieson
<p>We are given a ${\bf \it syntactic }$ complexity class ${\bf A}$ such that ${\bf P}$ $\subseteq$ ${\bf A}$ $\subseteq$ ${\bf PSPACE}$. Is it possible that ${\bf A}$ is ${\bf \it not}$ closed under any polynomial time reduction? Conversely, is there a default reduction that all ${\bf \it syntactic }$ complexity classes between ${\bf PSPACE}$ and ${\bf P}$ are closed under? (Such as ${\bf NP}$,${\bf C_{=}P}$, ${\bf PP}$, ... ) </p>

<p>A given language $L$ is in syntactic complexity class ${\bf A }$ if there exists a polynomial $p$ and a poynomial-time predicate $R$ such that, for each $x$</p>

<p>$x$ ${\in}$ $L$ ${\leftrightarrow}$ $||\{y|$  $ |y|=p(|x|) \wedge R(x,y)\}||$ is equal, less than, greater than... etc. a function that has $x$ as input.</p>

<p>$x$ ${\notin}$ $L$   otherwise. </p>

<p>Then the related problem is in that complexity class given the definition above. And the completeness follows from the parsimonious reductions of any problem in $\#{\bf P}$ to #SAT. Then is this class closed under some reduction by default?</p>

<p>For example, Complexity class ${\bf \oplus P}$ can be defined as follows:</p>

<p>A language $L$ is in syntanctic complexity class ${\bf \oplus P}$ if there exists a polynomial $p$ and a plynomial-time predicate $R$ such that, for each $x$ </p>

<p>$x$ ${\in}$ $L$ ${\leftrightarrow}$ $||\{y|$  $ |y|=p(|x|) \wedge R(x,y)\}||$ $\not\equiv$ 0 (mod 2).</p>

<p>$x$ ${\notin}$ $L$   otherwise.</p>

<p>Then Papadimitrou shows in his text book that ${\bf \oplus P}$-SAT is in ${\bf \oplus P}$ given the definition above and the completeness follows from the parsimonious reductions of any problem in $\#{\bf P}$ to #SAT. Does this imply that ${\bf \oplus P}$ is closed under some type of a reduction? such as, many-one, truth-table, conjunctive truth table,... etc. This is regardless of any other fact we might know about ${\bf \oplus P}$ such as the fact that we know ${\bf \oplus P}$ is low for itself, that is ${\bf \oplus P}$ = ${\bf \oplus P}^{\bf \oplus P}$ or ${\bf \oplus P}$ is closed under completed, that is ${\bf \oplus P}$ = ${\bf Co\oplus P}$</p>

<p>In general, when we define a complexity class like above and show that it has a complete problem, does that imply that this complexity class is closed under any type of a reduction. </p>

CC BY-SA 3.0
2012-08-01T12:03:37.937Z
Just as a comment aside from my answer, cstheory.SE isn't really the appropriate venue for this kind of question, it's meant for research level questions (see the [FAQ]). A better place would be cs.SE.
Luke Mathieson
CC BY-SA 3.0
2012-08-01T16:06:15.840Z
Voted to close. Besides the question not being research level, it isn't phrased very clearly either. And when people try to interpret your questions by asking questions, your answers are often uninformative and sometimes hostile. To quote your comment: "Guys I am not asking about this... Then I can go to any question, interpret it the way I want to and answer it..."
Robin Kothari
CC BY-SA 3.0
2012-08-01T16:24:35.680Z
@ Robin I even edited the question.. By the way, If the person that is attempting to answer my question begins the answer with " I'm not entirely clear on your notation" when the notation is pretty standard, I do not think they should answer it.
Tayfun Pay
CC BY-SA 3.0
2012-08-01T20:12:05.023Z
The question is still very unclear. By "outside P" do you mean "containing P"? Being outside a complexity class is normally used for languages not complexity classes. What do you mean by a "complexity class" and "any reduction"? I am asking there because the usual definitions I am familiar with don't seem to be what you mean: a "complexity class" is a family of subsets of $\Sigma^*$, a "reduction" is a set of functions over $\Sigma^*$.
Kaveh
CC BY-SA 3.0
2012-08-01T20:15:46.160Z
I also don't understand the later paragraphs. Please edit the question to make it clear and unambiguous, otherwise the question should be closed as not-a-real-question.
Kaveh
CC BY-SA 3.0
2012-08-02T14:13:44.427Z
@Kaveh You may close the question, delete it or whatever else you would like to do with it. I figured out that the complexity class I was working on is in fact closed under k - truth table reductions. Thank you for all your help.
Tayfun Pay
CC BY-SA 3.0
2012-08-02T22:24:20.467Z
I don't see why you have changed the tags, adding back [tag:soft-question] and removing [tag:cc.complexity-theory]. Please read the description of tags before using them. ps: A question is not just for you if you are posting it here, it's also for others who are using the site and should be understandable for them.
Kaveh
<cc.complexity-theory><reductions>
Are all complexity classes closed under a particular reduction?
Tayfun Pay
# Are all complexity classes closed under a particular reduction?

(Asked by: username_0 on 2012-08-01)

We are given a ${\bf \it syntactic }$ complexity class ${\bf A}$ such that ${\bf P}$ $\subseteq$ ${\bf A}$ $\subseteq$ ${\bf PSPACE}$. Is it possible that ${\bf A}$ is ${\bf \it not}$ closed under any polynomial time reduction? Conversely, is there a default reduction that all ${\bf \it syntactic }$ complexity classes between ${\bf PSPACE}$ and ${\bf P}$ are closed under? (Such as ${\bf NP}$,${\bf C\_{=}P}$, ${\bf PP}$, ... )

A given language $L$ is in syntactic complexity class ${\bf A }$ if there exists a polynomial $p$ and a poynomial-time predicate $R$ such that, for each $x$

$x$ ${\in}$ $L$ ${\leftrightarrow}$ $||\{y|$ $ |y|=p(|x|) \wedge R(x,y)\}||$ is equal, less than, greater than... etc. a function that has $x$ as input.

$x$ ${\notin}$ $L$ otherwise.

Then the related problem is in that complexity class given the definition above. And the completeness follows from the parsimonious reductions of any problem in $\#{\bf P}$ to #SAT. Then is this class closed under some reduction by default?

For example, Complexity class ${\bf \oplus P}$ can be defined as follows:

A language $L$ is in syntanctic complexity class ${\bf \oplus P}$ if there exists a polynomial $p$ and a plynomial-time predicate $R$ such that, for each $x$

$x$ ${\in}$ $L$ ${\leftrightarrow}$ $||\{y|$ $ |y|=p(|x|) \wedge R(x,y)\}||$ $\not\equiv$ 0 (mod 2).

$x$ ${\notin}$ $L$ otherwise.

Then Papadimitrou shows in his text book that ${\bf \oplus P}$-SAT is in ${\bf \oplus P}$ given the definition above and the completeness follows from the parsimonious reductions of any problem in $\#{\bf P}$ to #SAT. Does this imply that ${\bf \oplus P}$ is closed under some type of a reduction? such as, many-one, truth-table, conjunctive truth table,... etc. This is regardless of any other fact we might know about ${\bf \oplus P}$ such as the fact that we know ${\bf \oplus P}$ is low for itself, that is ${\bf \oplus P}$ = ${\bf \oplus P}^{\bf \oplus P}$ or ${\bf \oplus P}$ is closed under completed, that is ${\bf \oplus P}$ = ${\bf Co\oplus P}$

In general, when we define a complexity class like above and show that it has a complete problem, does that imply that this complexity class is closed under any type of a reduction.

**Tags:** cc.complexity-theory, reductions

> **Comments:**
> **username_1**: Just as a comment aside from my answer, cstheory.SE isn't really the appropriate venue for this kind of question, it's meant for research level questions (see the [FAQ]). A better place would be cs.SE.  
> **username_2**: Voted to close. Besides the question not being research level, it isn't phrased very clearly either. And when people try to interpret your questions by asking questions, your answers are often uninformative and sometimes hostile. To quote your comment: "Guys I am not asking about this... Then I can go to any question, interpret it the way I want to and answer it..."  
> **username_0**: @ Robin I even edited the question.. By the way, If the person that is attempting to answer my question begins the answer with " I'm not entirely clear on your notation" when the notation is pretty standard, I do not think they should answer it.  
> **username_3**: The question is still very unclear. By "outside P" do you mean "containing P"? Being outside a complexity class is normally used for languages not complexity classes. What do you mean by a "complexity class" and "any reduction"? I am asking there because the usual definitions I am familiar with don't seem to be what you mean: a "complexity class" is a family of subsets of $\Sigma^*$, a "reduction" is a set of functions over $\Sigma^*$.  
> **username_3**: I also don't understand the later paragraphs. Please edit the question to make it clear and unambiguous, otherwise the question should be closed as not-a-real-question.  
> **username_0**: @username_3 You may close the question, delete it or whatever else you would like to do with it. I figured out that the complexity class I was working on is in fact closed under k - truth table reductions. Thank you for all your help.  
> **username_3**: I don't see why you have changed the tags, adding back [tag:soft-question] and removing [tag:cc.complexity-theory]. Please read the description of tags before using them. ps: A question is not just for you if you are posting it here, it's also for others who are using the site and should be understandable for them.  

---

## 1 answers

### Answer by username_1 on 2012-08-01. Score: 5

I'm not entirely clear on your notation, but if you define a complexity class as the closure of a particular problem under PTIME reductions, then it will of course be closed under PTIME reductions.

On the other side, you can easily create a class $A$ that isn't closed under PTIME reductions, a trivial example would be to just pick a class that contains one $NP$-complete problem (say $A = \{SAT\}$). Is this what you mean?

A third point is that you can have classes that are closed, but have no complete problems - the Polynomial Hierarchy has no complete problems unless it collapses to finitely many levels (which seems unlikely).

> **Comments:**
> **username_4**: @Geekster: why not? All three things he has stated are pretty clearly correct. Any class defined as the **PTIME** closure of a problem will be **PTIME** closed; no single problem is **PTIME** closed; and his statement about **PH** is also correct. What specifically do you think is wrong?  
> **username_0**: @NieldeBeaudrap NP is not closed under any polynomial time reduction? How about CoNP? C=P or PP?  
> **username_4**: @Geekster: a singleton-set *S* consisting of any *single* **NP**-complete problem is not closed under **PTIME** reduction. After all, the closure of *S*  under **PTIME** reduction is **NP**, by definition, which contains more problems than *S* does.  
> **username_5**: But does {SAT} really qualify as a _complexity class_?  
> **username_4**: @JɛﬀE: it certainly isn't a very natural one, but is the lack of naturalness the only complaint? Would the situation be much improved if we took the closure of {SAT} under logarithmic-time reductions?  
> **username_0**: Guys I am not asking about this... Then I can go to any question, interpret it the way I want to and answer it...  
> **username_3**: @Geekster, the problem is that your question is vague. Luke's interpretation is consistent with what you have written. If this is not what you intended to ask then your question allows multiple interpretations. People cannot guess what is your intention, it is your responsibility to write questions in a clear way that is unambiguous and does not lead to multiple interpretations.  
> **username_3**: @JɛﬀE, do you know a definition of "complexity class" (of decision problems) other than a set of subsets of $\Sigma^*$?  

---

