all for more computing power to calculate the system's behavior, but the problem remains tractable in polynomial time (e.g., quadratic in the number of components): it A. Einstein, B. Podolsky, and N. Rosen, Can quantum-mechanical description of physical reality be consid- ered complete? Phys. Rev., 47 (1935), 777-80. Foreword is referred to as a "P" problem. Complexity is another story: "complex" has a different meaning here from "complicated." It is, rather, the intimate nature of the interaction between the different components (including, for instance, recursion) that governs the emergence of novel types and classes of macroscopic behavior. Complex systems show properties that are not predictable from the single analysis of their constitutive elements, just as the properties of entangled particles cannot be understood from the simple inference of single particule behaviors. In the last decades, complex systems have caused many developments in fields as varied as physics, astrophysics, chemistry, and biology. New mathematical tools, chaos, nonlinear physics, have been introduced. From the dynamics of sand dunes to schools of fishes, from ferrofluids to traffic jams, complexity never results from a simple extrap- olation of classical individual behaviors. Hence, the challenge of understanding and harnessing entanglement is the possibility of extending the perspectives of quantum mechanics in the same way that macroscopic physics was renewed by the introduction of complexity. Entanglement is the complexity of quantum mechanics. Considering this, it is not surprising that Shannon's classical theory of information (CIT) and quantum physics, with the emerging field of quantum information theory (QIT), have many background concepts in common. The former classical theory of information was a revolution in its own times, just as quantum mechanics, but with neither conceptual links, nor the least parallelism whatsoever with the latter. The great news is that the two fields have finally reached each other, in most unexp