One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large complexity class.This definitely makes sense for P and NP, but how about EXPTIME and NEXPTIME? So my question is this: What is the subset of NEXPTIME comprised of problems exp-time reducible from every other problem in NEXPTIME? If EXPTIME != NEXPTIME, is this class distinct from both NEXPTIME and NEXPTIME-complete?
NEXPTIME-completeness with more time for reductions
cc.complexity theory