Optimal replacement is NP-hard for nonstandard caches
Mark Brehob, Stephen Wagner, Eric K. Torng, Richard J. Enbody · IEEE Transactions on Computers · 2004
When examining a new cache structure or replacement policy, the optimal policy is a useful baseline. We prove that finding the optimal schedule is NP-hard for any but the simplest of caches, and that no polynomial-time approximation scheme exists for this problem unless P=NP.