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.

  • 6
    $\begingroup$ 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. $\endgroup$ – Luke Mathieson Aug 1 '12 at 12:03
  • 3
    $\begingroup$ 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..." $\endgroup$ – Robin Kothari Aug 1 '12 at 16:06
  • $\begingroup$ @ 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. $\endgroup$ – Tayfun Pay Aug 1 '12 at 16:24
  • $\begingroup$ 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^*$. $\endgroup$ – Kaveh Aug 1 '12 at 20:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 2 '12 at 22:24

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).

| cite | improve this answer | |
  • $\begingroup$ @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? $\endgroup$ – Niel de Beaudrap Aug 1 '12 at 14:50
  • 1
    $\begingroup$ But does {SAT} really qualify as a complexity class? $\endgroup$ – Jeffε Aug 1 '12 at 15:32
  • 3
    $\begingroup$ @JɛffE: 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? $\endgroup$ – Niel de Beaudrap Aug 1 '12 at 15:43
  • 5
    $\begingroup$ @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. $\endgroup$ – Kaveh Aug 1 '12 at 20:05
  • 4
    $\begingroup$ @JɛffE, do you know a definition of "complexity class" (of decision problems) other than a set of subsets of $\Sigma^*$? $\endgroup$ – Kaveh Aug 1 '12 at 20:08

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