For classes over NP (EXPTIME, EXPSPACE etc.) we define complete problems in terms of polynomial time reductions. I can understand that it is useful in cases of that class being equal to P, but it is highly unlikely. I think we should use corresponding limits for complexity classes. (polynomial space reduction for EXPTIME, exponential time reductions for EXPSPACE etc.). This will probably increase the size of complete problems for each class.
What do you think?
In complexity theory, we consider a variety of notions of reduction. However, completeness is only meaningful if you use a class of reductions from a potentially smaller class. Every non-trivial problem in PSPACE is complete for PSPACE under PSPACE reductions: the reduction simply solves the problem in question and produces an instance with the same value. On the other hand, it makes sense to talk about problems complete for EXP under PSPACE reductions, although I do not know of any such problems that are not also known to be complete under P reductions.
Thank you for your answer. It clarified my understanding. I also corrected the question accordingly.
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication