scientific article; zbMATH DE number 4001485

zbMath0617.68048MaRDI QIDQ4727431

Pekka Orponen, Osamu Watanabe, Ker-I. Ko, Uwe Schoening

Publication date: 1986

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

complexity classescomplexity corehard instance of a decision problemKolmogorov-complexity

Mathematics Subject Classification ID

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

Related Items

On resource-bounded instance complexity, In Memoriam: Ker-I Ko (1950–2018), Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity, Reductions to sets of low information content, Complexity indices for the multidimensional knapsack problem, Some consequences of the existnce of pseudorandom generators