On the IO-complexity and approximation languages

DOI10.1016/0020-0190(88)90139-1MaRDI QIDQ1112018zbMATH OpenOpenAlexFDO

Authors José Rolim, Sheila A. Greibach

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90139-1

zbMATH Keywords

approximation solutionsinfinitely oftenIO-complexity

Mathematics Subject Classification ID

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

Review text

The existence of intractable problems has raised several questions whether such problems can be solved ``on average. The present paper introduces the IO-complexity (the conditions meet infinitely often, in contrast with the traditional case when they are fulfilled almost everywhere), and studies some connections between it and the notion of approximation solutions.

Recommendations

• scientific article; zbMATH DE number 88935
• scientific article; zbMATH DE number 1072538
• On the theory of average case complexity
• Average-case non-approximability of optimisation problems
• scientific article; zbMATH DE number 5081744

Cites work

• A note on the best-case complexity
• Average time analyses of simplified Davis-Putnam procedures
• Determining the Chromatic Number of a Graph
• Solving low-density subset sum problems
• The NP-completeness column: An ongoing guide

Cited in

(2)

• Computing the optimal IO sequences of a protocol in polynomial time
• On the polynomial IO-complexity

This page was built for publication: On the IO-complexity and approximation languages

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