Almost complete

From Wikipedia, the free encyclopedia

In computer science, a problem is almost complete for a complexity class C if it is both in C and "many" other problems in C reduce to it. More specifically, the subset of problems of C which reduce to the problem is a measure one set, in terms of Lutz's resource bounded measure. This is a weaker requirement than the problem being complete for the class.