Instance complexity

DOI10.1145/174644.174648MaRDI QIDQ4299297zbMATH OpenOpenAlexFDO

Authors Pekka Orponen, Osamu Watanabe, Ker-I Ko, Uwe Schöning

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

zbMATH Keywords

Kolmogorov complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Resource-bounded instance complexity
• On resource-bounded instance complexity
• An instance level analysis of data complexity
• Average-Case Complexity
• scientific article; zbMATH DE number 5081744
• scientific article; zbMATH DE number 512870
• scientific article; zbMATH DE number 1161563
• scientific article; zbMATH DE number 863498
• scientific article; zbMATH DE number 3810920
• scientific article; zbMATH DE number 218387

Cited in

(25)

• Generic properties of a computational task predict human effort and performance
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• The structure of logarithmic advice complexity classes
• An excursion to the Kolmogorov random strings
• Proof systems that take advice
• Resource bounded immunity and simplicity
• Upper bounds for the complexity of sparse and tally descriptions
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Fixed-parameter decidability: extending parameterized complexity analysis
• The frequent paucity of trivial strings
• Reductions to sets of low information content (extended abstract)
• Resource-bounded instance complexity
• Average-case intractability vs. worst-case intractability
• A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem
• In Memoriam: Ker-I Ko (1950–2018)
• Generation Complexity Versus Distinction Complexity
• On resource-bounded instance complexity
• A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality
• scientific article; zbMATH DE number 3874610 (Why is no real title available?)
• scientific article; zbMATH DE number 403953 (Why is no real title available?)
• Nondeterministic Instance Complexity and Proof Systems with Advice
• Kolmogorov complexity and non-determinism
• On hard instances
• scientific article; zbMATH DE number 3984572 (Why is no real title available?)

This page was built for publication: Instance complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4299297)