Random strings make hard instances

DOI10.1006/JCSS.1996.0067zbMath0859.68034OpenAlexW2146811744MaRDI QIDQ1816733

Pekka Orponen, Harry Buhrman

Publication date: 27 November 1996

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

Full work available at URL: https://ir.cwi.nl/pub/1379

zbMATH Keywords

Kolmogorov random stringsKolmogorov complexities

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

On resource-bounded instance complexity ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ On hard instances

This page was built for publication: Random strings make hard instances