Near-Testable Sets

DOI10.1137/0220033zbMath0738.68031OpenAlexW2083557874MaRDI 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

zbMATH Keywords

one-way functionself-reducibilitystructural complexity theorynear-testabilityparity polynomial time

Mathematics Subject Classification ID

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

Related Items (7)

Sets computable in polynomial time on average ⋮ On sets polynomially enumerable by iteration ⋮ Strong self-reducibility precludes strong immunity ⋮ Reducibility classes of P-selective sets ⋮ On the power of parity polynomial time ⋮ On the size of classes with weak membership properties ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem

This page was built for publication: Near-Testable Sets