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?

  • $\begingroup$ I'm not sure I understand your question. Hardness and therefore completness is defined with respect to the same type of reducibility. Then you ask for the set of languages which are in NEXPTIME(subset) and, if I understand correctly, are NEXPTIME-hard(reduce 'from'). Obviously, this is the class NEXPTIME-complete. Depending on whether you consider completeness w.r.t ptime many-to-one reductions or exptime many-to-one, or any other type of reduction, this class can differ. $\endgroup$ – John D. Jul 23 '14 at 8:07
  • $\begingroup$ Right, to clarify my question is about the "this class can differ". Has anyone proved whether or not the set NEXPTIME-complete (w/ ptime-reduction) is distinct from the set NEXPTIME-complete (w/ exptime-reduction)? $\endgroup$ – Kurt Mueller Jul 23 '14 at 11:51
  • $\begingroup$ Sorry if this question is too simplistic. Suppose $x$ is an instance of an NEXPTIME problem, it seems that the reduction process must preserve the size of the instance by running in polynomial-time. Do you have any problem instance that requires EXPTIME to produce (by reduction) another problem instance? $\endgroup$ – lgidwani Jul 28 '14 at 16:04
  • $\begingroup$ A trivial example is that we have an exponential time reduction from every single problem in EXPTIME to any other problem by simply solving the EXPTIME problem. The existence of a less trivial example is the goal of asking this question :) $\endgroup$ – Kurt Mueller Jul 29 '14 at 14:00

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.