Title :
On sets with efficient implicit membership tests
Author :
Hemachandra, Lane A. ; Hoene, Albrecht
Author_Institution :
Dept. of Comput. Sci., Rochester Univ., NY, USA
Abstract :
The complexity of implicit membership testing is characterized in terms of the well-known complexity class OptP, optimization polynomial time. It is concluded that many complex sets have polynomial-time implicit membership tests. Thus, the complexity of implicit membership testing is closely related to the complexity of optimization
Keywords :
computational complexity; set theory; OptP; complex sets; complexity class; efficient implicit membership tests; implicit membership testing; optimization polynomial time; Computer science; Polynomials; Testing; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113950
