I wonder why can't I allow an exponential-time reduction from all problems in $\textbf{NEXP}$ to a language $L$ and claim $L$ to be $\text{NEXP-complete}$.

The computational complexity class $\text{NEXPTIME}$ or $\text{NEXP}$ has been defined here. In the same page, there is a section on $\text{NEXP-complete}$. This section states that the reduction must polynomial time. For the case of the deterministic version of this class, we can not have exponential time reductions as having exponential time reduction leads to all problems in $\textbf{EXP}$ be $\textbf{EXP-complete}$.

This reasoning is also held for the class $\textbf{P}$, which is why we have log-space reductions defined here. But when we are talking about $\textbf{NP}$ we deal with polynomial-time reductions. By same logic, I should be allowed exponential-time reductions for $\textbf{NEXP}$.


1 Answer 1


The complete statement about completeness for complexity classes is "Problem A is complete for complexity class B under C-reductions."

In many cases it is clear from the context what notion of reducibility we are using, and so we can get away with not mentioning it explicitly. For P-completeness, it is clear that we mean logspace reductions if not stated otherwise, for NP-completeness we mean polytime reductions unless stated otherwise. The wiki page you link is clarifying that they are using polytime reductions for NEXP-completeness, too.

Of course you can go and study completeness for NEXP under EXP-reductions. But since "Problem A is complete for NEXP under EXP-reductions." is a much weaker statement than "Problem is complete for NEXP under polytime reductions.", it would be preferable to make the latter statement whenever you can prove it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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