Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

714 general harder than problems in P. The P versus N P problem asks for a proof that the complexity classes P and N P really are distinct. For a detailed discussion of the problem, see computational complexity [IV.20]. V. Theorems and Problems these structures are the three-dimensional versions of Euclidean, spherical, and hyperbolic geometry (see [I.3 §6]). Another is the infinite "cylinder" S 2 × R : that is, the product of a 2-sphere with an infinite line. Simi- larly, one can take the product of the hyperbolic plane with an infinite line and obtain a fifth structure. The other three are slightly more complicated to describe. Thurston also gave significant evidence for his con- jecture by proving it in the case of so-called Haken manifolds. The geometrization conjecture implies the Poincaré conjecture; both were proved by Grigori Perelman, who completed a program that had been set out by Richard Hamilton. The main idea of this program was to solve the problems by analyzing ricci flow [III.78]. The solu- tion was announced in 2003 and checked carefully by several experts over the next few years. For more details, see differential topology [IV.7]. V.25 The Poincaré Conjecture The Poincaré conjecture is the statement that a com- pact [III.9] smooth n-dimensional manifold that is homotopy equivalent [IV.6 §2] to the n-sphere S n must in fact be homeomorphic to S n . One can think of a compact manifold as a manifold that lives in a finite region of R m for some m and that has no boundary: for example, the 2-sphere and the torus are compact manifolds living in R 3 , while the open unit disk or an infinitely long cylinder is not. (The open unit disk does not have a boundary in an intrinsic sense, but its realization as the set {(x, y) : x 2 + y 2 < 1} has the set {(x, y) : x 2 + y 2 = 1} as its boundary.) A manifold is called simply connected if every loop in the manifold can be continuously con- tracted to a point. For instance, a sphere of dimen- sion greater than 1 is simply connected but a torus is not (since a loop that "goes around" the torus will always go around the torus, however you continuously deform it). In three dimensions, the Poincaré conjec- ture asks whether two simple properties of spheres, compactness and simple connectedness, are enough to characterize spheres. The case n = 1 is not interesting: the real line is not compact and a circle is not simply connected, so the hypotheses of the problem cannot be satisfied. poincaré [VI.61] himself solved the problem for n = 2 early in the twentieth century, by completely classify- ing all compact 2-manifolds and noting that in his list of all possible such manifolds only the sphere was simply connected. For a time he believed that he had solved the three-dimensional case as well, but then discov- ered a counterexample to one of the main assertions of his proof. In 1961, Stephen Smale proved the con- 5, and Michael Freedman proved the jecture for n n = 4 case in 1982. That left just the three-dimensional problem open. Also in 1982, William Thurston put forward his famous geometrization conjecture, which was a pro- posed classification of three-dimensional manifolds. The conjecture asserted that every compact 3-manifold can be cut up into submanifolds that can be given metrics [III.56] that turn them into one of eight par- ticularly symmetrical geometric structures. Three of V.26 The Prime Number Theorem and the Riemann Hypothesis How many prime numbers are there between 1 and n? A natural first reaction to this question is to define (n) to be the number of prime numbers between 1 and n and to search for a formula for (n). However, the primes do not have any obvious pattern to them and it has become clear that no such formula exists (unless one counts highly artificial formulas that do not actually help one to calculate (n)). The standard reaction of mathematicians to this kind of situation is to look instead for good estimates. In other words, we try to find a simply defined func- tion f (n) for which we can prove that f (n) is always a good approximation to (n). The modern form of the prime number theorem was first conjectured by gauss [VI.26] (though a closely related conjecture had been made by legendre [VI.24] a few years earlier). He looked at the numerical evidence, which suggested to him that the "density" of primes near n was about 1/log n, in the sense that a randomly chosen integer near n would have a probability of roughly 1/log n of being a prime. This leads to the conjectured approx- imation of n/log n for (n), or to the slightly more sophisticated approximation n (n) 0 dx . log x The function defined by the integral on the right-hand side is called li(n) (which stands for the "logarithmic