On Sets with Efficient Implicit Membership Tests

DOI10.1137/0220071MaRDI QIDQ3985813zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, 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

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

Recommendations

• scientific article; zbMATH DE number 403952
• Representing sets with constant time equality testing
• Near-Testable Sets

Cited in

(8)

• On sets polynomially enumerable by iteration
• On the size of classes with weak membership properties
• Asymptotic properties of set membership identification algorithms
• Universally serializable computation
• scientific article; zbMATH DE number 403952 (Why is no real title available?)
• Reductions to sets of low information content (extended abstract)
• SELF-SPECIFYING MACHINES
• Reducibility classes of P-selective sets

This page was built for publication: On Sets with Efficient Implicit Membership Tests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3985813)