Hard-core theorems for complexity classes

DOI10.1145/2455.214111zbMath0632.68047OpenAlexW2080325829MaRDI QIDQ3769964

Selman, Alan L., Yacov Yacobi, Shimon Even

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2455.214111

zbMATH Keywords

randomized algorithmsautomata-based complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items

Nonlevelable sets and immune sets in the accepting density hierarchy inNP, NP is as easy as detecting unique solutions, On solving hard problems by polynomial-size circuits, A classification of complexity core lattices, Classifying the computational complexity of problems