HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

What is complexity class $\oplus P^{\oplus P}$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
oplusclasscomplexitywhat

Problem

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

Solution

$\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.

Context

StackExchange Computer Science Q#1836, answer score: 11

Revisions (0)

No revisions yet.