A comparison of polynomial time completeness notions (Q1097692): Difference between revisions

Several types of polynomial time reductions for the superpolynomial decision problem class \(DEXT=\cup \{DTIME(2^{cn})|\) \(c>0\}\) are considered. The purpose of the paper is to characterize the differences between polynomial time completeness notions for DEXT with respect to any pair of the above reductions. The author succeeds to prove all but two differences for the class DEXT. An interesting open problem is whether or not the obtained results hold also for complexity classes specified by nondeterministic machines.