Separating NP-Completeness Notions under
โ
Klaus Ambos-Spies; Levke Bentzien
๐
Article
๐
2000
๐
Elsevier Science
๐
English
โ 227 KB
Lutz (1993, ``Proceedings of the Eight Annual Conference on Structure in Complexity Theory, '' pp. 158 175) proposed the study of the structure of the class NP=NTIME( poly) under the hypothesis that NP does not have p-measure 0 (with respect to Lutz's resource bounded measure (1992, J. Comput. Syste