8
$\begingroup$

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?

$\endgroup$

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.