Instance complexity
From MaRDI portal
Publication:4299297
DOI10.1145/174644.174648zbMath0807.68035OpenAlexW2293341947MaRDI QIDQ4299297
Osamu Watanabe, Pekka Orponen, Uwe Schoening, Ker-I. Ko
Publication date: 1 March 1995
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10138/243065
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On resource-bounded instance complexity ⋮ An excursion to the Kolmogorov random strings ⋮ Average-case intractability vs. worst-case intractability ⋮ A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Weak completeness in \(\text{E}\) and \(\text{E}_{2}\) ⋮ A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem ⋮ The frequent paucity of trivial strings ⋮ Proof systems that take advice ⋮ Kolmogorov complexity and non-determinism ⋮ Reductions to sets of low information content ⋮ Nondeterministic Instance Complexity and Proof Systems with Advice ⋮ The structure of logarithmic advice complexity classes ⋮ On hard instances ⋮ Resource bounded immunity and simplicity
