Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is just for fun and this is completely outside my area, so it's likely dumb; apologies in advance.

By a "quotient" I mean the following: suppose you have two complexity classes, $A \subseteq B$. The quotient $B/A$ would consist of the equivalence classes of elements of $B$ under the relation $b \sim b'$ if you can solve $b'$ with a program from $A$ given input from an oracle for $b$, and vice-versa. (I don't know if this concept has a name or is called something else; sorry.)

(To give the obvious example, the $P$ versus $NP$ problem asks whether $NP/P$ is trivial.)

Can anything interesting be said about this notion?

share|cite|improve this question

I think it is extensively studied under oracle turing machines. Here is an example from this book.

Let $EXPCOM$ = $\{<M,x,1^n>:$ M outpits 1 in $2^n$ steps.$\}$

Now consider $P^{EXPCOM}/EXP$ along with your definition.

Clearly $EXP\subseteq P^{EXPCOM}$. Now for two problem $(b,b')$ which is in $P^{EXPCOM}$ and if there is a polynomial time reduction from $b\leq_P b'$, then it creates a equivalence class since a program from $EXP$ (which just do the polynomial time reduction and queries the given oracle TM) can solve b'.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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