Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another.

However, if we consider larger complexity classes such as NEXP or NEEXP, can we define a new type of reduction which gives the reduction more time.

I realise that we have the problem that if we allow an exptime reduction $EXP^A$ for some oracle A, then given an input $x$ to the machine, we can boost the input to the oracle A to have length $O(2^{|x|})$. This gives us too much power as if, for example A=NEXP, then allowing this essentially allows us to solve NEEXP problems.

However, can we define a more useful/valid reduction where we are only allowed to query the oracle with a $poly(|x|)$ input, or the input to the oracle is required to be in unary? Has this already been investigated somewhere in the literature?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.