On limited nondeterminism and the complexity of the V-C dimension
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.<>Keywords
This publication has 14 references indexed in Scilit:
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Classes of bounded nondeterminismTheory of Computing Systems, 1990
- On finding a minimum dominating set in a tournamentTheoretical Computer Science, 1988
- How easy is local search?Journal of Computer and System Sciences, 1988
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- A deterministic view of random sampling and its use in geometryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Results on learnability and the Vapnik-Chervonenkis dimensionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Games against natureJournal of Computer and System Sciences, 1985
- Refining Nondeterminism in Relativized Polynomial-Time Bounded ComputationsSIAM Journal on Computing, 1980
- Two theorems on random polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978