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

IO-complexityapproximation solutionsinfinitely often

Mathematics Subject Classification ID

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

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)

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

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)