The proof of the theorem is based on a reduction from the vertex-cover problem. The theorem shows that even in a very restricted case, the problem is intractable. Our setting is especially simple because it does not even consider non-trivial queries over the data. It is important to note that the NP-hardness is in the size of the network. This theorem should not dampen our enthusiasm regarding the data placement problem—quite the contrary. The challenge is to find more specific settings in which to study the problem, where the network and workloads have interesting properties that can be exploited. A version of the problem that.
