On the size of classes with weak membership properties

DOI10.1016/S0304-3975(97)00114-XzbMath0912.68048MaRDI QIDQ1274925

Marius Zimand

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

resource-bounded measureP-selective setscheatable setseasily approximable setseasily countable setslocally self-reducible setsnear-testable setsnearly near-testable setsP-bi-immune setsP-multiselective sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Relative to a random oracle, P/poly is not measurable in EXP

Cites Work

• Unnamed Item
• Almost everywhere high nonuniform complexity
• Almost every set in exponential time is P-bi-immune
• Process complexity and effective random tests
• Optimal Approximations and Polynomially Levelable Sets
• Near-Testable Sets
• On Sets with Efficient Implicit Membership Tests
• Polynomial Time Productivity, Approximations, and Levelability
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Polynomial-Time Membership Comparable Sets

This page was built for publication: On the size of classes with weak membership properties