On Sets with Efficient Implicit Membership Tests

DOI10.1137/0220071zbMath0738.68032OpenAlexW2013274327MaRDI QIDQ3985813

Hemaspaandra, Lane A., Albrecht Hoene

Publication date: 27 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/2014736f5214b7953df445058ee425c862f462aa

zbMATH Keywords

membership testingoptimization polynomial time

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Universally serializable computation, On sets polynomially enumerable by iteration, Reducibility classes of P-selective sets, Reductions to sets of low information content, On the size of classes with weak membership properties, SELF-SPECIFYING MACHINES