Caching Is Hard—Even in the Fault Model

• DOI: 10.1007/s00453-011-9502-9
• Publication Date: 2011-03-09T21:11:28Z
• Authors: Marek Chrobak; Gerhard J. Woeginger; Kazuhisa Makino; Haifeng Xu
• Keywords: Paging; Theory of computation; Completeness (order theory)

We prove strong ${\mathbb {NP}}$ -completeness for the four variants of caching with multi-size pages. These are obtained by choosing either fault cost or bit model, and combining it a forced an optional policy. This resolves two questions in area paging that were open since 1990s.