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 nO(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 :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2200886
بازگشت