All natural NP-complete problems have average-case complete versions

DOI10.1007/S00037-010-0298-9MaRDI QIDQ626691zbMATH OpenOpenAlexFDO

Authors Noam Livne

Publication date 18 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-010-0298-9

zbMATH Keywords

average case complete problemsaverage case complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 5081744
• scientific article; zbMATH DE number 1008518
• scientific article; zbMATH DE number 512870
• Average case complexity, revisited
• On the theory of average case complexity

Cited in

(11)

• On the NP-isomorphism problem with respect to random instances
• On the average-case complexity of parameterized clique
• Average case complexity, revisited
• An encoding invariant version of polynomial time computable distributions
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• scientific article; zbMATH DE number 1008518 (Why is no real title available?)
• Complexity of distributions and average-case hardness
• All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size
• Rankable distributions do not provide harder instances than uniform distributions
• Average case complexity theory
• Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs

This page was built for publication: All natural NP-complete problems have average-case complete versions

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