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$?

Improve this question
$\endgroup$
2
  • 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
    Commented May 14, 2012 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
    Commented May 14, 2012 at 16:48

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
10
  • $\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
    Commented May 14, 2012 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
    Commented May 14, 2012 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
    Commented May 14, 2012 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
    Commented May 14, 2012 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
    Commented May 15, 2012 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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