The problems of data placement are investigated abstractly, and we use the theory of NP-completeness to prove some results which indicate the level of difficulty of some increasingly realistic data placement problems. As a consequence of these theorems it is established that the likelihood of finding a deterministic algorithm to solve any of these data placement problems with acceptable performance is very small, and other, possibly heuristic, methods are suggested. A particularly interesting data placement problem considered in this study is formulated as the layered data placement problem, which is shown to be NP-complete.