On limited nondeterminism and the complexity of the V-C dimension
Christos H. Papadimitriou, Mihalis Yannakakis · 2002
The complexity of several natural computational problems in NP, which have been proposed but not categorized satisfactorily in the literature is characterized precisely. These problems can be solved in n/sup O(logn)/ time, and thus they are probably not NP-complete. Two new complexity classes between P and NP, very much in the spirit of MAXNP and MAXSNP, are defined. It is shown that computing the V-C dimension is complete for the more general class, whereas the other two problems are complete for the weaker class.>