On the polynomial IO-complexity

DOI10.1016/0020-0190(89)90141-5zbMath0689.68069OpenAlexW2009806555MaRDI QIDQ582102

José D. P. Rolim

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90141-5

zbMATH Keywords

densitysparsenessNPEIO-complexityNEPtally sets

Mathematics Subject Classification ID

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

Cites Work

• On the IO-complexity and approximation languages
• A note on the best-case complexity
• On sparse sets in NP-P
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Completeness, Approximation and Density
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Tally languages and complexity classes
• On Effective Procedures for Speeding Up Algorithms

This page was built for publication: On the polynomial IO-complexity