Resource-bounded measure has been defined on the classes E, E/sub 2/, ESPACE, E/sub 2/SPACE, REC, and the class of all languages. It is shown here that if C is any of these classes and X is a set of languages that is closed under finite variations and has outer measure less than 1 in C, then X has measure 0 in C. This result strengthens Lutz's resource-bounded generalization of the classical Kolmogorov zero-one law. It also gives a useful sufficient condition for proving that a set has measure 0 in a complexity class.

The effect of query order on NP-completeness is investigated. A sequence D/spl I.oarr/=(D/sub 1/,...,D/sub k/) of decision problems is defined to be sequentially complete for NP if each D/sub i//spl isin/NP and every problem in NP can be decided in polynomial time with one query to each of D/sub 1/,...,D/sub k/ in this order. It is shown that, if NP contains a language that is p-generic in the sense of Ambos-Spies, Fleischhack, and Huwig (1987), then for every integer k/spl ges/2, there is a sequence D/spl I.oarr/=(d/sub 1/,...,D/sub k/) such that D is sequentially complete for NP, but no nontrivial permutation (D(i/sub 1/),...,D(i/sub k/)) of D/spl I.oarr/ is sequentially complete for NP. It follows that such a sequence D/spl I.oarr/ exists if there is any strongly positive, p-computable probability measure /spl nu/ such that "/sub p/(NP)/spl ne/0.