DocumentCode
2200886
Title
On limited nondeterminism and the complexity of the V-C dimension
Author
Papadimitriou, Christos H. ; Yannakakis, Mihalirr
Author_Institution
California Univ., San Diego, La Jolla, CA, USA
fYear
1993
fDate
18-21 May 1993
Firstpage
12
Lastpage
18
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 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
computational complexity; MAXNP; MAXSNP; V-C dimension; complexity; limited nondeterminism; Circuits; Inspection; Land mobile radio; Polynomials; Virtual colonoscopy;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location
San Diego, CA
Print_ISBN
0-8186-4070-7
Type
conf
DOI
10.1109/SCT.1993.336545
Filename
336545
Link To Document