Smoothed complexity theory

DOI10.1145/2656210MaRDI QIDQ6829920zbMATH OpenFDO

Authors Markus Bläser, Bodo Manthey

Publication date 24 October 2016

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://research.utwente.nl/en/publications/c7dabcbf-8c11-4e0b-92d1-c45117712c91

zbMATH Keywords

computational complexitysmoothed analysisaverage-case complexity

Mathematics Subject Classification ID

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

This page was built for publication: Smoothed complexity theory

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