Hard-core theorems for complexity classes

DOI10.1145/2455.214111zbMATH Open0632.68047OpenAlexW2080325829MaRDI QIDQ3769964FDOQ3769964

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

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
• Publication:4728249
• scientific article; zbMATH DE number 1088223

zbMATH Keywords

randomized algorithmsautomata-based complexity classes

Mathematics Subject Classification ID

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

Cited In (11)

• Title not available (Why is that?)
• On solving hard problems by polynomial-size circuits
• A classification of complexity core lattices
• Title not available (Why is that?)
• NP is as easy as detecting unique solutions
• Dichotomy theorems for families of non-cofinal essential complexity
• Title not available (Why is that?)
• 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)