# Are all complexity classes closed under a particular reduction? [closed]

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.

• 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 Aug 1 '12 at 12:03
• 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 Aug 1 '12 at 16:06
• @ 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 Aug 1 '12 at 16:24
• 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 Aug 1 '12 at 20:12
• I don't see why you have changed the tags, adding back soft-question and removing 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 Aug 2 '12 at 22:24

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?
• @JɛﬀE, do you know a definition of "complexity class" (of decision problems) other than a set of subsets of $\Sigma^*$? – Kaveh Aug 1 '12 at 20:08