Near-Testable Sets
From MaRDI portal
Publication:3978780
DOI10.1137/0220033zbMath0738.68031MaRDI QIDQ3978780
No author found.
Publication date: 25 June 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0220033
one-way function; self-reducibility; structural complexity theory; near-testability; parity polynomial time
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Strong self-reducibility precludes strong immunity, Reducibility classes of P-selective sets, On sets polynomially enumerable by iteration, On the size of classes with weak membership properties, A second step towards complexity-theoretic analogs of Rice's Theorem