ON LIMITED NONDETERMINISM AND THE COMPLEXITY OF THE V-C DIMENSION

We characterize precisely the complexity of several natural computatio nal problems in NP, which have been proposed but not categorized satis factorily in the literature: Computing the Vapnik-Chervonenkis dimensi on of a 0-1 matrix; finding the minimum dominating set of a tournament ; satisfying a Boolean expression by perturbing the default truth assi gnment; and several others. These problems can be solved in n(O(log n) ) time, and thus, they are probably not NP-complete. We define two new complexity classes between P and NP, very much in the spirit of MAXNP and MAXSNP. We show that computing the V-C dimension is complete for the more general class, while the other two problems are complete for the weaker class. (C) 1996 Academic Press. Inc.