On Sets with Efficient Implicit Membership Tests
Lane A. Hemaspaandra, Albrecht Hoene · SIAM Journal on Computing · 1991
This paper completely characterizes the complexity of implicit membership testing in terms of the well-known complexity class OptP, optimization polynomial time, and concludes that many complex sets have polynomial-time implicit membership tests.