Take the 2-minute tour ×

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|improve this question

1 Answer 1

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|improve this answer

Your Answer


