12
$\begingroup$

What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing machine $M$ such that $x \in A$ iff the number of accepting states of the machine $M$ on the input $x$ is odd.

But what does $\oplus P^{\oplus P}$ mean? I just can't follow what it actually does :)

What are practical consequences of such complexity class and how it is possible to show that $\oplus P^{\oplus P} = \oplus P$?

$\endgroup$
  • 2
    $\begingroup$ This (imho awkward) notation denotes relative or oracle complexity classes. See Wikipedia for a definition. Does that answer the question? If not, please edit to clarify. $\endgroup$ – Raphael May 14 '12 at 16:27
  • 7
    $\begingroup$ You'll find the proof of $\oplus P^{\oplus P} = \oplus P$ at cs.rutgers.edu/~allender/538/murata3.pdf $\endgroup$ – sdcvvc May 14 '12 at 16:48
11
$\begingroup$

$\oplus P^{\oplus P}$ denotes the class $\oplus P$ equipped with what's known as an oracle for $\oplus P$ — we say that it has been given the ability to determine whether or not a string $s$ is a member of a language $L$ contained in the class $\oplus P$ in a single operation.

I see that another commenter (sdcwc) has linked to the proof of $\oplus P^{\oplus P} = \oplus P$ (see these notes on a lecture from CS 538 at Rutgers). A complexity class $C$ that is an oracle to a class $B$ such that $B^C= B$, is said to be low for the class $B$. In this case, we say that $\oplus P$ is low for itself.

$\endgroup$
  • $\begingroup$ Another link for you, this time to the wikipedia page on 'lowness' of complexity classes: en.wikipedia.org/wiki/Low_%28complexity%29 $\endgroup$ – Josh Lockhart May 14 '12 at 18:45
  • $\begingroup$ Your style of the explanation is sufficient for the understanding of the basic principles and it is easy to follow. $\endgroup$ – stewenson May 14 '12 at 19:42
  • $\begingroup$ What do you basically mean that $\oplus P$ is equipped with the oracle which can determine membership of the language $L$ in the single step? From my point of view, if you are about solving some problem in $\oplus P^{\oplus P}$, you are querying the oracle in the very beginning of the computation so after the first step, you know how the oracle answers you? So you know that since you've reached one acceptance state, the number of such states is just one, so the odd number, so you accept? $\endgroup$ – stewenson May 14 '12 at 19:44
  • 3
    $\begingroup$ "an oracle for $\oplus P$ - we say that it has been given the ability to determine whether or not a language $L$ is a member of $\oplus P$ in a single operation." - this is incorrect: An oracle gives the ability to determine whether a string $s$ is a member of some language $L$ in $\oplus P$. Without loss of generality, $L$ can be taken to be $\oplus SAT$ (since it is $\oplus P$-complete) $\endgroup$ – sdcvvc May 14 '12 at 20:17
  • $\begingroup$ I am trying to follow the proof really hard but it is quite unclear to me. For example, what does function $f(1^i,x)$ mean? I know it is "repeat 1 i times ($1^3 = 111$)" but what is it good for in this context? What does specially $1^i$ mean? And what about the $k$ in $n^k$ everywhere? If $i \leq n^k$, then $f(1^i,x) = f(1^{n^k}, x) = f(1^{|x|^k}, x)$. What does it mean? Why you have a function $f \in \sharp P$ with such input? $\endgroup$ – stewenson May 15 '12 at 0:24

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.