Weak completeness in E and E2

The notions of weak ⩽m P-completeness for the complexity classes E = DTIME(2linear) and E2 = DTIME(2polynomial) are compared. An element C of one of these classes is weakly ⩽m P- complete for the class if the set Pm(C), consisting of all languages A ⩽m P C, does not have measure 0 in the class. The following two results are proven. 1. (i)|Every problem that is weakly ⩽m P-complete for E is weakly ⩽m P-complete for E2. 2. (ii)|There is a problem in E that is weakly ⩽m P-complete for E2, but not for E.

Authors

• David W. Juedes
• Jack H. Lutz

Keywords

No keywords are indexed for this paper.