Caching Is Hard—Even in the Fault Model
Marek Chrobák, Gerhard J. Woeginger, Kazuhisa Makino, Haifeng Xu · Algorithmica · 2011
We prove strong ${\mathbb {NP}}$ -completeness for the four variants of caching with multi-size pages. These four variants are obtained by choosing either the fault cost or the bit cost model, and by combining it with either a forced or an optional caching policy. This resolves two questions in the area of paging and caching that were open since the 1990s.