Instance complexity
From MaRDI portal
Publication:4299297
DOI10.1145/174644.174648zbMath0807.68035MaRDI 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
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Upper bounds for the complexity of sparse and tally descriptions, Kolmogorov complexity and non-determinism, Proof systems that take advice, Average-case intractability vs. worst-case intractability, Weak completeness in \(\text{E}\) and \(\text{E}_{2}\), The structure of logarithmic advice complexity classes, On resource-bounded instance complexity, An excursion to the Kolmogorov random strings, On hard instances, A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem, Resource bounded immunity and simplicity, Nondeterministic Instance Complexity and Proof Systems with Advice