{unblock|Start 2008-10-22T06:00:03 Going to read /Users/fly818/var/cpan/Metadata
Database was generated on Wed, 22 Oct 2008 10:26:54 GMT
Running make for D/DB/DBARTLE/WWW-DomainTools-0.11.tar.gz Fetching with LWP:
http://cpan.nas.activestate.com/authors/id/D/DB/DBARTLE/WWW-DomainTools-0.11.tar.gz
Fetching with LWP:
http://cpan.nas.activestate.com/authors/id/D/DB/DBARTLE/CHECKSUMS
Checksum for /Users/fly818/var/cpan/sources/authors/id/D/DB/DBARTLE/WWW-DomainTools-0.11.tar.gz ok WWW-DomainTools-0.11/ WWW-DomainTools-0.11/Build.PL WWW-DomainTools-0.11/Changes WWW-DomainTools-0.11/lib/ WWW-DomainTools-0.11/lib/WWW/ WWW-DomainTools-0.11/lib/WWW/DomainTools/ WWW-DomainTools-0.11/lib/WWW/DomainTools/NameSpinner.pm WWW-DomainTools-0.11/lib/WWW/DomainTools/SearchEngine.pm WWW-DomainTools-0.11/lib/WWW/DomainTools.pm WWW-DomainTools-0.11/LICENSE WWW-DomainTools-0.11/Makefile.PL WWW-DomainTools-0.11/MANIFEST WWW-DomainTools-0.11/META.yml WWW-DomainTools-0.11/README WWW-DomainTools-0.11/t/ WWW-DomainTools-0.11/t/001_load.t WWW-DomainTools-0.11/t/002_search_engine.t WWW-DomainTools-0.11/t/003_name_spinner.t WWW-DomainTools-0.11/t/004_custom_user_agent.t WWW-DomainTools-0.11/t/license.yml
CPAN.pm: Going to build D/DB/DBARTLE/WWW-DomainTools-0.11.tar.gz
>>> /Users/fly818/bin/perl Makefile.PL Checking if your kit is complete... Looks good Writing Makefile for WWW::DomainTools >>> make cp lib/WWW/DomainTools/NameSpinner.pm blib/lib/WWW/DomainTools/NameSpinner.pm cp lib/WWW/DomainTools.pm blib/lib/WWW/DomainTools.pm cp lib/WWW/DomainTools/SearchEngine.pm blib/lib/WWW/DomainTools/SearchEngine.pm Manifying blib/man3/WWW::DomainTools::NameSpinner.3 Manifying blib/man3/WWW::DomainTools.3 Manifying blib/man3/WWW::DomainTools::SearchEngine.3
DBARTLE/WWW-DomainTools-0.11.tar.gz make -- OK
Running make test >>> make test TEST_VERBOSE=1 PERL_DL_NONLAZY=1 /Users/fly818/bin/perl "-MExtUtils::Command::MM" "-e" "test_harness(1, 'blib/lib', 'blib/arch')" t/*.t t/001_load................. 1..4 ok 1 - use WWW::DomainTools::NameSpinner; ok 2 - use WWW::DomainTools::SearchEngine; ok 3 - NameSpinner instantiated ok 4 - SearchEngine instantiated ok t/002_search_engine........ 1..9 ok 1 - use WWW::DomainTools::SearchEngine; ok 2 - default set 1 ok 3 - default set 2 ok 4 - default set 3 ok 5 - default set 4 ok 6 - response came back ok 7 # SKIP no commercial license edit t/license.yml ok 8 # SKIP no commercial license edit t/license.yml ok 9 # SKIP no commercial license edit t/license.yml ok t/003_name_spinner......... 1..6 ok 1 - use WWW::DomainTools::NameSpinner; ok 2 - default set 1 ok 3 - default set 2 ok 4 - default set 3 ok 5 - default set 4 ok 6 - response came back ok t/004_custom_user_agent.... 1..3 ok 1 - use WWW::DomainTools::NameSpinner; ok 2 - customer user agent doesn't look like default ok 3 - custom user agent passed in ok All tests successful. Files=4, Tests=22, 2 wallclock secs ( 0.08 usr 0.07 sys + 1.76 cusr 0.44 csys = 2.35 CPU) Result: PASS
DBARTLE/WWW-DomainTools-0.11.tar.gz make test TEST_VERBOSE=1 -- OK
<SOFTPKG NAME="WWW-DomainTools" VERSION="0.11" DATE="2008-05-22">
<AUTHOR CPAN="DBARTLE">David Bartle <captindave@gmail.com></AUTHOR> <ABSTRACT>Interface with domaintools.com XML API</ABSTRACT> <ARCHITECTURE NAME="darwin-thread-multi-2level-5.8"/> <CODEBASE HREF="WWW-DomainTools-0.11.tar.gz"/> <PROVIDE NAME="WWW::DomainTools" VERSION="0.11"/> <PROVIDE NAME="WWW::DomainTools::NameSpinner" VERSION="1.03"/> <PROVIDE NAME="WWW::DomainTools::SearchEngine" VERSION="0.06"/> <REQUIRE NAME="HTTP::Request"/> <REQUIRE NAME="LWP::UserAgent"/> <REQUIRE NAME="Test::Simple" VERSION="0.44"/> <REQUIRE NAME="URI::Escape"/> <REQUIRE NAME="XML::Simple"/> <REQUIRE NAME="YAML::"/>
</SOFTPKG> >>> (cd /Users/fly818/var/cpan/build/WWW-DomainTools-0.11-doqNCQ && tar cvf - WWW-DomainTools-0.11.ppd blib) | gzip -c >/Users/fly818/var/REPO/D/DB/DBARTLE/WWW-DomainTools-0.11.tar.gz WWW-DomainTools-0.11.ppd blib/ blib/lib/ blib/lib/WWW/ blib/lib/WWW/DomainTools/ blib/lib/WWW/DomainTools/NameSpinner.pm blib/lib/WWW/DomainTools/SearchEngine.pm blib/lib/WWW/DomainTools.pm blib/man3/ blib/man3/WWW::DomainTools.3 blib/man3/WWW::DomainTools::NameSpinner.3 blib/man3/WWW::DomainTools::SearchEngine.3 >>> mv /Users/fly818/var/cpan/build/WWW-DomainTools-0.11-doqNCQ/WWW-DomainTools-0.11.ppd /Users/fly818/var/REPO/D/DB/DBARTLE Finished 2008-10-22T06:00:11}David Eppstein
[P=NP]
editK-THEORY OF A WALDHAUSEN CATEGORY AS A SYMMETRIC SPECTRUM MITYA BOYARCHENKO Abstract. If C is a Waldhausen category (i.e., a “category with cofibrations and weak equivalences”), it is known that one can define its K-theory K(C) as a connective symmetric
-spectrum. The goal of these notes is to explain the construction in such a way that it can be not only understood, but also (hopefully) remembered by a non-expert. We do not claim that our exposition shows the process by which Waldhausen has originally discovered his definition of K(C), nor do we assert that our approach leads to a deeper understanding of algebraic K-theory. We simply try to remove as much “mystery” as possible from the multi-step construction of the spectrum K(C). 1. Introduction. Let C be a Waldhausen category (the precise definition appears later in this text). The original construction of Waldhausen ([Wa83], § 1.3) produces from C a certain simplicial Waldhausen category, usually denoted by S•C, with the following property. If we look at the subcategory w(S•C) of S•C whose objects are all the objects of S•C and whose morphisms are the weak equivalences in S•C, take its nerve N•(w(S•C)), which is a bisimplicial set, and form its geometric realization |N•(w(S•C))|, the homotopy groups of the resulting topological space are the K-groups of C up to a shift; more precisely, Ki(C) = �i+1|N•(w(S•C))| 8i � 0. [At least with the classical approach, this equality is an (easy) theorem for i = 0, and a definition for i > 0.] In the rest of these notes, we ask the reader to take on faith the following three principles, which we are unable to motivate, but which (if understood appropriately) will lead to a modern definition of K(C) as a connective symmetric -spectrum. (1): The space whose homotopy groups compute the higher K-theory of C is obtained as the classifying space of a certain simplicial category w(S•C). (2): The n-th term of this simplicial category has something to do with n-step filtrations of objects in C, 0 = A0 / /A1 / / . . . / /An = A. (3): If one wants to define K(C) as a spectrum rather than a space, one needs to iterate the S•-construction (this is possible because each term SnC will also be a Waldhausen category, as mentioned above). Moreover, the iterations can be performed in a symmetric way (i.e., one which is independent of the order in which the iterations are being made), and this will lead to a definition of K(C) as a symmetric spectrum. The reader is advised to look through at least §§ 1.1 – 1.3 of [Wa83], since a lot of what follows was motivated by those sections. In particular, a glance at the proof of Lemma 1.1.5 in op. cit. shows that Waldhausen was fully aware of the possibility of Date: August 11, 2006. 1 2 MITYA BOYARCHENKO formulating his iterated S•-construction in a symmetric way, only he did not have the adequate language of symmetric spectra to describe the result. The actual definition of K(C) that we give at the end of these notes is contained in the very densely written § 6.1 of [GH97]. A lot of the work shown below was done in order to explain how one could deduce the various ingredients in the definition in loc. cit. from the three principles stated above. 2. Categories with cofibrations. Almost all of our constructions will only deal with cofibrations, and weak equivalences will appear at the very end. Thus we begin with Definition ([Wa83], § 1.1): A category with cofibrations is a pair (C, co(C)) consisting of a category C that has a zero object 0 (i.e., an object which is both initial and terminal) and a subcategory co(C) � C whose morphisms are called cofibrations in C and are represented pictorially as A / /B, satisfying the following three axioms. Cof 1.: All isomorphisms in C are contained in co(C) (in particular, as a subcategory, co(C) contains all objects of C). Cof 2.: For each object A 2 C, the unique arrow 0 −! A is a cofibration. Cof 3.: Cofibrations admit “cobase change”. This means that if A / f / g � B C is a diagram in C (where f is a cofibration), then the pushout C [ A B exists, and, moreover, the induced arrow C −! C [ A B is also a cofibration: C / / C [ A B. Informally speaking, one should think of cofibrations as being analogous to monomorphisms, and one should think of a category with cofibrations as a category where one has a good notion of a monomorphism which is stable under pushouts. Example: Let A be an abelian category, and let P � A be an exact subcategory, i.e., a strict full additive subcategory which is stable under extensions. We define the cofibrations in P to be the admissible monomorphisms, i.e., arrows A f −! B in P that are monomorphisms in A and are such that Coker(f) 2 P. This makes P into a category with cofibrations; the only nontrivial axiom to verify is Cof 3. In order to check it, let A / f /B be an admissible monomorphism in P, and let A g −! C be any arrow in P. We have a diagram in A 0 /A (f,−g) /B � C / proj1 � C [ A B / ' � 0 0 /A f /B / Coker f / 0 K-THEORY OF A WALDHAUSEN CATEGORY 3 with exact rows. It induces an isomorphism C �= Ker(proj1) �= Ker ', which shows that the induced morphism i : C ! C [A B is a monomorphism in A. In addition, ' is epimorphic, so since C 2 P and Coker f 2 P by assumption, we see that C [ A B 2 P as well. And, finally, we also see that Coker i �= Coker f 2 P, which implies that i is an admissible monomorphism in P and completes the proof. In what follows, the reader would not miss any part of the explanations by restricting attention to the special class of categories with cofibrations arising from exact categories P in the way described above. Indeed, one may even assume that P = A is abelian; moreover, this case will constantly be used as a motivation for more general constructions involving cofibrations. 3. Filtrations and quotients. It is clear that once we have a suitable analogue of a monomorphism, we can also define filtrations. It will be convenient for us to assume that all our filtrations start with the zero object. Thus, if C is a category with cofibrations, we define an n-step filtration of an object A 2 C to be a sequence of cofibrations 0 = A0 / /A1 / /A2 / / . . . / /An = A. The next observation is that the notion of “quotient by a subobject” makes sense in C. Namely, if A / f /B is a cofibration in C, then, by axiom Cof 3, the pushout of f and the unique arrow A −! 0 exists; we will denote it by B/A = 0 [A B and represent the natural arrow B −! B/A as follows: B / /B/A . Thus we have a pushout diagram A / / � B ���� 0 /B/A A sequence of the form A / /B / /B/A will be referred to as a cofibration sequence. Note that the choice of B/A is not quite unique: it is only unique up to canonical isomorphism. Let us now return to principles (1) and (2) stated above. The n-th term SnC of the simplicial category S•C will essentially be the category of all sequences of cofibrations of the form 0 = A0 / /A1 / / . . . / /An . To understand why this is not good enough, recall that we need to have n+1 “face functors” SnC ! Sn−1C corresponding to the n+1 strictly increasing maps {0, 1, . . . , n − 1} = [n − 1] ! [n] = {0, 1, . . . , n}. It is easy to guess n of them: they are obtained by omitting Aj from the sequence (where 1 � j � n) and replacing the two cofibrations Aj−1 / /Aj / /Aj+1 with their composition (if j 6= n). However, we need one more face functor, and we can not define by simply omitting A0 since we have agreed that all our filtrations start with the zero objects. What we do instead is omit A0 and quotient out everything else by A1. However, we now run into the problem of making functorial choices of the quotients Aj/A1 for all 2 � j � n. More generally, if we try to define other structure maps SnC ! SkC of a simplicial category, we will see that we will need to make functorial choices of all the 4 MITYA BOYARCHENKO possible subquotients Aj/Ai (1 � i < j � n). Waldhausen’s solution is to keep track of these choices from the very beginning. Thus he defines a category which is equivalent to the category of n-step filtrations 0 / /A1 / /A2 / / . . . / /An , whose objects are such filtrations together with compatible choices of all subquotients Aj/Ai. More precisely, this means that we look at the category of commutative triangular diagrams of the form (�) 0 = A00 / /A01 / / ���� A02 / / ���� . . . / /A0n ���� 0 = A11 / / A12 / / ���� . . . / /A1n ���� 0 = A22 / / . . . . . . / /A2n ... 0 = Ann with the property that each composition Aij / /Aik /Ajk is a cofibration sequence. One passes from such a diagram to an n-step filtration by ignoring everything except for the first row, and one goes the other way by starting with an n-step filtration 0 = A0 / /A1 / /A2 / / . . . / /An , choosing subquotients Aij := Aj/Ai, and filling in all the other arrows in the diagram above using the universal property of pushouts and the axiom Cof 3. A nice way of restating the definition of the diagram (�), which will be crucial for the more complicated constructions below, is as follows. Consider the linearly ordered set [n] = {0, 1, 2, . . . , n} as a category in the usual way. Then a diagram of the form (�) is the same thing as a functor Ar[n] −!C, (i ! j) 7−!Ai!j = Aij , where Ar[n] is the arrow category of [n], that has the following properties: (i) : Ai!j = 0 whenever i = j; (ii) : for each composable pair of arrows i ! j and j ! k, the morphism Ai!j −! Ai!k is a cofibration; (iii): for each composable pair of arrows i ! j and j ! k, the sequence Ai!j / /Ai!k /Aj!k is a cofibration sequence in C. We note that the property (iii) is an analogue of the Second Isomorphism Theorem in algebra: (Ak/Ai)/(Aj/Ai) �= Ak/Aj . With this notation, we define SnC to be the category of functors Ar[n] ! C satisfying properties (i) – (iii) above, the morphisms in SnC being natural transformations. When K-THEORY OF A WALDHAUSEN CATEGORY 5 formulated this way, the definition becomes manifestly functorial with respect to nondecreasing maps [m] ! [n], and so we obtain a simplicial category S•C, as promised. 4. Iteration. According to principle (3), we now need to iterate this construction. It already suffices to consider the case n = 2 because the general case is philosophically the same. Thus we consider the category S2C, which can be naturally identified with the category of cofibration sequences in C, A / /B / /B/A , (��) the morphisms being the obvious commutative diagrams. If we want to be able to iterate the S•-construction, we need to equip S2C with a class of cofibrations. A natural desire is to define cofibrations in S2C to be such that the three natural functors S2C ///// C obtained by sending (��) to A, B, and B/A, respectively, are exact, and in particular preserve cofibrations. Thus the most obvious guess is that a cofibration in S2C is a commutative diagram of the form A1 / / � � B1 / / � � B1/A1 � � A2 / /B2 / /B2/A2 However, when we define cofibrations this way, we lose symmetry: the diagram above is not symmetric under switching A2 and B1. In order to keep the symmetry we discard the quotients and look at squares of the form A1 / / � � B1 � � A2 / /B2 (� � �) In order to understand the condition we need to impose on this square, let us return to the motivating example where C = A is an abelian category. Thus we are given an object B2 of A and three subobjects A1,B1,A2 � B2 such that A1 � B1 \ A2. Then there is an induced morphism B1/A1 ! B2/A2, and it is a trivial exercise to check that it is a monomorphism if and only if A1 = B1 \ A2. Of course, this condition (taken literally) does not make sense in a general category with cofibrations; however, one of the first observations in [Wa83] is that in an abelian category, we have A1 = B1 \ A2 if and only if the induced morphism B1 [A1 A2 −! B2 is a monomorphism. Now this property certainly has an analogue in an arbitrary category with cofibrations, and we take it as our definition. Proposition-Definition ([Wa83], Lemma 1.1.1): Define a cofibration in the category F1(C) of cofibrations A / /B in C to be a commutative square of the form (� � �) such that the induced arrow B1 [A1 A2 −! B2 is also a cofibration. This makes F1(C) into a category with cofibrations. The main point is that the condition that B1 [A1 A2 / /B2 is symmetric with respect to switching A2 and B1. Moreover, we can now iterate this construction, obtaining 6 MITYA BOYARCHENKO categories F1F1(C), F1F1F1(C), and so on. These multiple iterations can be organized in an economical and symmetric way using the following notion. 5. Cofibration cubes. Let Q be a finite set. Let P(Q) = 2Q denote its power set, viewed as a partially ordered set with respect to inclusion, and hence as a category. Definition: A Q-cube in a category C is a functor X : P(Q) ! C. Examples: (0) If Q = ?, then P(Q) = {?}, and hence an ?-cube in C is just an object of C. (1) If Q = {1}, then P(Q) = {?, {1}}, and hence a 1-cube in C is an arrow in C. (2) If Q = {1, 2}, then P(Q) = {?, {1}, {2}, {1, 2}}, and the inclusion relations are {2} � [ {1, 2} [ ? � {1}, so a 2-cube in C is a commutative square X01 /X11 X00 O /X10 O (3) It should by now be obvious what is going on in higher dimensions. Here is a picture of a 3-cube: X011 /X111 X001 x; xx xx xx x /X101 x; xx xx xx x X010 O /X110 O X000 O x; xx xx xx x /X100 O x; xx xx xx x The point is that in order to specify the action of X on the arrows of P(Q), it is enough to look at arrows of the form S ! T, where S � T � Q are subsets such that S and T differ by exactly one element. Definition (Important!): Let C be a category with cofibrations. A Q-cube X : P(Q) ! C is said to be a cofibration cube if for each pair of subsets S & T � Q, the induced morphism lim −! S�U&T X(U) −! X(T) (†) is a cofibration in C. As we explain below, the colimit in this definition can be formed by iterated pushouts along cofibrations in C, and therefore exists. Examples: (0) Every ?-cube in C is a cofibration cube. K-THEORY OF A WALDHAUSEN CATEGORY 7 (1) A cofibration 1-cube in C is the same as an arrow X0 ! X1 in C which is a cofibration. (2) A cofibration 2-cube in C is a commutative square of the form X01 / /X11 X00 O O / /X10 O O with the additional property that the induced arrow X01 [X00 X10 ! X11 is a cofibration. We see that cofibration 2-cubes in C are the same as cofibrations in the category F1(C). Thus, as promised, cofibration cubes provide a generalization of the latter notion. (3) A cofibration 3-cube in C is a commutative 3-cube, drawn above, such that each of its faces is a cofibration 2-cube, and such that the induced arrow colim 0 BBBBBB@ X100 / FF F F" FF X110 X000 x< xx xx xx x / F" FF FF FF F X010 x< xx xx xx x F" FF FF FF F X101 X001 xx x x< xx /X011 1 CCCCCCA −! X111 is a cofibration. It is a simple exercise to check that the colimit on the left can be constructed as X101 [ X100 X110 ! [ X001 S X000 X010 X011 and therefore it exists. Moreover, in case C arises from an abelian category A, we see that giving a cofibration cube in A amounts to giving an object X111 = X of A together with three subobjects A = X110, B = X101, C = X011, satisfying the properties A \ (B + C) = (A \ B) + (A \ C), B \ (A + C) = (B \ A) + (B \ C), C \ (A + B) = (C \ A) + (C \ B). All the other vertices of the cube can be recovered from A, B, C as follows: X100 = A \ B, X010 = A \ C, X001 = B \ C, X000 = A \ B \ C. Higher-dimensional cofibration cubes can be interpreted in a similar way, using induction on dimension. The main point to keep in mind is that a Q-cube is a cofibration cube if and only if its faces are cofibration cubes in lower dimensions, and it satisfies an extra condition corresponding to taking S = ? and T = Q in the definition. 6. Multifiltrations. We return to the main question of how to iterate the S•-construction in general. Since one iteration corresponds to looking at filtrations, a natural guess is that in general one has to look at multifiltrations. As usual, we first illustrate the approach for an abelian category A. Moreover, for now we will only work with bifiltrations, since passing to general Q-filtrations only requires an understanding of bifiltrations and of cofibration cubes, discussed above. Thus let ~n = (n1, n2) be a pair of 8 MITYA BOYARCHENKO nonnegative integers, let A be an object of an abelian category A, and assume that A is equipped with two filtrations: (0) = F(1) 0 A � F(1) 1 A � . . . � F(1) n1 A = A and (0) = F(2) 0 A � F(2) 1 A � . . . � F(2) n2 A = A. In the case of ordinary filtrations, we saw that we needed to keep track of all possible subquotients. The correct analogue of this for bifiltrations is to keep track of all possible double subquotients, defined as follows. If (i1, i2) and (j1, j2) are pairs of integers satisfying 0 � i1 � j1 � n1 and 0 � i2 � j2 � n2, then we can form a subquotient gr(1) i1!j1 A := F(1) j1 A/F(1) i1 A, which inherits a filtration induced by the second filtration A, and we can form gr~i!~j A := F(2) j2 � gr(1) i1!j1 A � F(2) j1 � gr(1) i1!j1 A �. To see that this definition is independent of the order in which the subquotients are taken, note that we can rewrite gr~i!~j A = � F(1) j1 A � \ � F(2) j2 A � � F(1) j1 A � \ � F(2) i2 A � + � F(1) i1 A � \ � F(2) j2 A �, and this expression is manifestly symmetric with respect to i1 � j1 and i2 � j2. In addition, this construction has the following properties: (i): If i1 = j1 or i2 = j2, then gr~i!~j A = 0. (ii): Let (k1, k2) = ~k be another pair satisfying 0 � iq � jq � kq � nq (q = 1, 2). Then the square gr(i1,i2)!(j1,k2) A � gr(i1,i2)!(k1,k2) A gr(i1,i2)!(j1,j2) A S | � gr(i1,i2)!(k1,j2) A S | is a cofibration square in A. (iii): In the same situation, the sequence 0 / gr(i1,i2)!(j1,k2) A � S gr(i1,i2)!(j1,j2) A gr(i1,i2)!(k1,j2) A � gr(i1,i2)!(k1,k2) A � gr(j1,j2)!(k1,k2) A / 0 K-THEORY OF A WALDHAUSEN CATEGORY 9 is exact. In fact, (ii) is a special case of (iii), but we separate them for psychological reasons. Property (iii) is a natural 2-dimensional analogue of the Second Isomorphism Theorem, stating that if A � B � C are subobjects in an abelian category, then the sequence 0 ! B/A ! C/A ! C/B ! 0 is exact. Finally, let Q be any finite set, and let 44 Q be the product of copies of the category 44 indexed by Q. Thus the objects of 44 Q are represented by [~n], where ~n = (nq)q2Q is a Q-tuple of nonnegative integers. We recall that a Q-simplicial set in any category D is a functor 44 Q�op ! D. Now if [~n] 2 44 Q, then [~n] itself can be viewed as a category since it is a partially ordered set: if~i = (iq)q2Q and ~j = (jq)q2Q, then ~i �~j () iq � jq for all q. If A is an object of an abelian category A equipped with a Q-filtration: 0 = F(q) 0 A � F(q) 1 A � . . . � F(q) nq A = A for all q, then, generalizing the previous constructions, we define gr~i!~j A = T q2Q FjqA � P q2Q
FiqA \ T t6=q FjtA !. These subquotients satisfy natural analogues of the properties (i) – (iii) above, and with all this in mind we can finally give the 7. Construction of K(C) as a symmetric spectrum. First recall the following Definition ([Wa83], § 1.2): If C is a category with cofibrations, a category of weak equivalences in C is a subcategory w(C) � C whose morphisms are called weak equivalences in C and are represented graphically as A � −! B, satisfying the following two axioms: Weq 1: All isomorphisms in C are contained in w(C) (in particular, all objects of C lie in w(C)). Weq 2: Gluing lemma for weak equivalences: given a diagram B o � o o A o � / C o � B0 o o A0 / C0 the induced arrow B [A C ! B0 [A0 C0 is also a weak equivalence. 10 MITYA BOYARCHENKO Main construction: Let Q be a finite set and let [~n] 2 44 Q, viewed as a category in the way explained above. Given any arrow~i !~j in [~n] and a subset U � Q, we define (~i !~j)U to be the arrow in [~n] whose q-th component is iq ! jq for q 2 U, and iq ! iq for q 62 U. It is easy to see that the assignment U 7−! (~i !~j)U defines a Q-cube in the category of arrows Ar[~n]. Let SQ ~n C be the full subcategory of the category of functors A : Ar[~n] −! C (~i !~j) 7−! A~i!~j (where C is a fixed category with cofibrations and weak equivalences) consisting of the functors satisfying the following three properties: (i): If iq = jq for some q 2 Q, then A~i!~j = 0. (ii): For every pair of composable arrows~i !~j !~k, the cube U 7−! A(~j !~k)U�(~i!~j) is a cofibration cube in C. (iii): Under the same assumption, the sequence lim −! U&Q A(~j!~k)U�(~i!~j) / /A~i!~k /A~j !~k is a cofibration sequence in C. We define a weak equivalence in SQ ~n C to be a natural transformation f : A ! A0 such that for each (~i !~j) 2 Ar[~n], the morphism f~i!~j : A~i!~j ! A0 ~i ! ~j is a weak equivalence in C. Thus we obtain a Q-simplicial category wSQ • C = � [~n] 7−! wSQ ~n C � . Observe that S?C = C in a natural way, and therefore wS?C = wC. By taking the classifying space of each of the categories wSQ ~n C, we obtain a pointed Q-simplicial topological space 44 Q�op −! Top = � topological spaces � , [~n] 7−! B � wSQ ~n C � . The reason it is pointed is that whenever nq = 0 for some q, the category SQ ~n C is the trivial one consisting just of the zero object of C. Moreover, if we think of B wSQ • C � as a presheaf of topological spaces on the category 44 Q, this presheaf is equivariant with respect to the natural action of Aut(Q) �= symmetric group on |Q| letters K-THEORY OF A WALDHAUSEN CATEGORY 11 on 44 Q. This implies that when we pass to the diagonal, diag B wSQ • C �� is a simplicial topological space with a natural action of Aut(Q). Finally, for each m � 0, let us pick a finite set Q with m elements, and set K(C)m = �� diag B wSQ • C ���� , the geometric realization of the simplicial topological space diag B wSQ • C �� . This is a topological space P (in fact a CW complex) with a natural action of the symmetric group m on m letters. To describe K(C) as a symmetric spectrum, it remains to define the structure maps S1 ^ K(C)m ! K(C)m+1 for all m � 0. However, observe that if Q = {1, 2, . . . ,m} and Q0 = {1, 2, . . . ,m + 1}, and for each ~n = (n1, . . . , nm) we define ~n0 = (n1, . . . , nm, 1), then the category SQ0 ~n0 C is naturally equivalent to SQ ~n C. (Informally speaking, when we pass from SQ ~n C to SQ0 ~n0 C, we add the extra data of a 1-step filtration in the (m+1)st direction, but the data of a 1-step filtration amounts to no data at all.) The natural inclusion SQ ~n C ' SQ0 ~n0 C ,! SQ0 • C yields, by adjunction, the maps S1 ^ K(C)m ! K(C)m+1, which are the structure maps of the symmetric spectrum K(C). Theorem (Essentially proved by Waldhausen modulo the fact that he did not use the term “symmetric spectrum”): K(C) is a connective symmetric spectrum, which is an
-spectrum beyond the term K(C)0. References [GH97] T. Geisser and L. Hesselholt, Topological cyclic homology of schemes, in: “Algebraic K-theory (Seattle, WA, 1997)”, 41–87, Proc. Sympos. Pure Math. 67, Amer. Math. Soc., Providence, RI, 1999. [HSS00] M. Hovey, B. Shipley and J. Smith, Symmetric spectra, J. Amer. Math. Soc. 13 (2000), no. 1, 149–208. [Wa83] F. Waldhausen, Algebraic K-theory of spaces, in: “Algebraic and geometric topology (New Brunswick, N.J., 1983)”, 318–419, Lecture Notes in Math. 1126, Springer, Berlin, 1985.Musatov (talk) 13:49, 3 May 2009 (UTC)
P=NP, Executive Summary on Math and Science
editP=NP, EXECUTIVE SUMMARY ON MATH AND SCIENCE Technologies’ Best Opportunity for Expansion, The singly most important unresolved question in computer science and complex number theory is the question: 𝐷𝑜𝑒𝑠 𝑃=𝑁𝑃? If P does not equal NP Our knowledge of the universe and technology is restricted. Certain elements of computation and logic are simply governed by natural laws of physics grounded in chaos theory. If P does equal NP The Universe is a highly ordered place governed by certain truths grounded in fundamental physics. We will continue to discover, through mathematics, science, and technology, vast new frontiers. The Expert Opinions: “If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...” — Scott Aaronson, MIT Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required. —Anil Nerode, Cornell University P=NP, EXECUTIVE SUMMARY ON MATH AND SCIENCE Technologies’ Best Opportunity for Expansion HOW TO UNDERSTAND P VERSUS NP Courtesy of the Clay Mathematics Institute: Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971. (To reference Mr. Cook’s description of the problem: http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf) CHAPTER 1 𝑻𝑯𝑬 𝑷 𝑽𝑬𝑹𝑺𝑼𝑺 𝑵𝑷 𝑺𝑶𝑳𝑼𝑻𝑰𝑶𝑵 MARTIN M. MUSATOV 1. STATEMENT OF THE SOLUTION This solution to P versus NP explains how every language accepted by some non deterministic algorithm in polynomial time can be accepted by some (deterministic) algorithm in polynomial time. To define the solution it is formally it is necessary to observe the model of a computer, or Turing machine and process information in real-time as it is received as a computable function or linear stream. Formally, the class P contains the in decision problems P= ⋯⋮⋱⋮⋯ 𝑁 ⋯⋮⋱⋮⋯ 𝑃 Continue the expansion: Area of a Circle: 𝐴=𝜋𝑟2 Binomial Theorem: 𝑥+𝑎 𝑛= 𝑛𝑘 𝑥𝑘𝑎𝑛−𝑘𝑛𝑘=0 Expansion of a Sum: 1+𝑥 𝑛=1+𝑛𝑥1!+𝑛 𝑛−1 𝑥22!+⋯ Fourier series: 𝑓 𝑥 =𝑎0+ 𝑎𝑛cos𝑛𝜋𝑥𝐿+𝑏𝑛sin𝑛𝜋𝑥𝐿 ∞𝑛=1 Pythagorean Theorem: 𝑎2+𝑏2=𝑐2 Quadratic Formula: 𝑥=−𝑏± 𝑏2−4𝑎𝑐2𝑎 Taylor Expansion: 𝑒𝑥=1+𝑥1!+𝑥22!+𝑥33!+⋯,−∞<𝑥<∞ Trig Identity 1: sin𝛼±sin𝛽=2sin12 𝛼±𝛽 cos12 𝛼∓𝛽 Trig Identity 2: cos𝛼+cos𝛽=2cos12 𝛼+𝛽 cos12 𝛼−𝛽 Conclusion: Binary revisions are allowed given the above formulas.