Structural average case complexity

DOI10.1006/jcss.1996.0024zbMath0855.68042OpenAlexW2048783513MaRDI QIDQ1916530

Rainer Schuler, Tomoyuki Yamakami

Publication date: 27 January 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/01da7e4e2efbfe77e8587a7f47bb8dbed63b4e23

zbMATH Keywords

average-case complexity measurepolynomial on average

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (3)

Average-case intractability vs. worst-case intractability ⋮ Sets computable in polynomial time on average ⋮ Polynomial time samplable distributions

This page was built for publication: Structural average case complexity