Hard-core theorems for complexity classes

DOI10.1145/2455.214111MaRDI QIDQ3769964zbMATH OpenOpenAlexFDO

Authors Shimon Even, Alan L. Selman, Yacov Yacobi

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)

Recommendations

• Complexity of hard-core set proofs
• scientific article; zbMATH DE number 4095440
• scientific article; zbMATH DE number 2212170
• Complexity bounds on general hard-core predicates.
• On the relative complexity of hard problems for complexity classes without complete problems
• The recursion-theoretic structure of complexity classes
• Hardness assumptions in the foundations of theoretical computer science
• Complexity classes as mathematical axioms
• scientific article; zbMATH DE number 4003531
• scientific article; zbMATH DE number 1088223

Cited in

(11)

• On solving hard problems by polynomial-size circuits
• A classification of complexity core lattices
• scientific article; zbMATH DE number 4095440 (Why is no real title available?)
• scientific article; zbMATH DE number 7378390 (Why is no real title available?)
• NP is as easy as detecting unique solutions
• Dichotomy theorems for families of non-cofinal essential complexity
• scientific article; zbMATH DE number 1500548 (Why is no real title available?)
• Hardness assumptions in the foundations of theoretical computer science
• Hardness of fully dense problems
• Nonlevelable sets and immune sets in the accepting density hierarchy inNP
• Classifying the computational complexity of problems

This page was built for publication: Hard-core theorems for complexity classes

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