Newsgroups: sci.math.research From: svasi@cs.uoregon.edu (Nathan Tenny) Subject: Re: computability of higher homotopy groups Date: Sat, 15 Apr 1995 00:49:40 GMT In article <3mh4eo$ha3@quabbin.crl.dec.com>, Maurice Herlihy wrote: >Given a finite simplicial complex, it it possible to compute a presentation >of the complex's higher homotopy groups? Even for the limited case of pi_2 of a 2-complex, probably not. Collapse a maximal tree in the 1-skeleton, so that you have a CW-complex K with a single 0-cell; if the simplicial complex was finite, K is a presentation model. Let L be the universal cover of K (or use a terminal that can put a tilde over the K :-), and build the cellular chain complex. By a Hurewicz argument, pi_2(K) is the kernel of the boundary map d_2:C_2(L) -> C_1(L). The rub is this: that map d_2 is a homomorphism of free modules over the group ring Z(pi_1(K)), and there aren't a whole lot of restrictions on it. To even find a set of generators for pi_2(K) as a Z(pi_1(K))-module, you have to be able to tell when things are killed by d_2, which means that you have to be able to do computations in the group ring pretty effectively. But to decide if an element of Z(pi_1(K)) is zero, you have to be able to solve the word problem in pi_1(K) (in case your element is a difference of two words). Hard to do! It's possible that d_2 has some special properties that make its kernel computable in general; is anything known in that direction? NT -- Nathan Tenny @ I do not believe that the same God topologist and loose cannon @ who endowed us with reason and intellect svasi@cs.uoregon.edu @ also intended us to forgo their use. tenny@euclid.uoregon.edu @ -Galileo [Mod. note: What about pi_n of a simplicial complex known to be 1-connected? Greg] ============================================================================== Newsgroups: sci.math.research From: lrudolph@panix.com (Lee Rudolph) Subject: Re: computability of higher homotopy groups Date: Sat, 15 Apr 1995 20:41:44 GMT Maurice Herlihy : >>Given a finite simplicial complex, it it possible to compute a presentation >>of the complex's higher homotopy groups? svasi@cs.uoregon.edu (Nathan Tenny): >Even for the limited case of pi_2 of a 2-complex, probably not. [argument omitted] Greg: >[Mod. note: What about pi_n of a simplicial complex known to >be 1-connected? Greg] Bingo! I quote from the MR review (by P. J. Hilton) of Edgar Brown's _Finite Computability of Postnikov complexes_ (Ann. of Math. (2) 65 (1957), 1-20): "The main results of this paper are the following: (1) If X is a simply-connected finite simplicial complex, then \pi_n(X) is finitely computable for all n ; (2) if X, Y are simply-connected finite simplicial complexes with finite homlogy groups, then there is a finite procedure for deciding whether they have the same homotopy type; (3) if X is a simply-connected finite simplicial complex with finite homology groups and Y is a finite simplicial complex, then there is a finite procedure for the homotopy classification of maps of Y into X." I confess that this leaves me a bit unsatisfied, since, given a finite simplicial complex, it isn't usually computable--is it?--whether or not X is simply connected. Lee Rudolph ============================================================================== Newsgroups: sci.math.research From: greg@dent.uchicago.edu (Greg Kuperberg) Subject: Re: computability of higher homotopy groups Date: Sun, 16 Apr 1995 22:10:13 GMT In article <3mpb28$i1m@panix.com>, Lee Rudolph wrote: >Bingo! I quote from the MR review (by P. J. Hilton) of Edgar Brown's >_Finite Computability of Postnikov complexes_ (Ann. of Math. (2) 65 >(1957), 1-20): > >"The main results of this paper are the following: (1) If X is a >simply-connected finite simplicial complex, then \pi_n(X) is >finitely computable for all n; ... >I confess that this leaves me a bit unsatisfied, since, given >a finite simplicial complex, it isn't usually computable--is >it?--whether or not X is simply connected. It's equivalent to the halting problem, which means that it's recursively enumerable but not recursive. I.e., if an oracle tells you that two finitely presented groups (presented by simplicial complexes, perhaps) are isomorphic, then you can eventually find a proof, although it might take you a very long time. This leads to the question: Suppose that you have a simplicial complex and an oracle tells you that the fundamental group is G. For which G can you compute the homotopy groups of the complex? For example, how about G = Z or G = SL_2(Z)? G finite is of course handled by Brown's theorem, and presumably his method can be extended to find the G-module structure of pi_n. ============================================================================== Newsgroups: sci.math.research From: hovey@schauder.math.mit.edu (Mark Hovey) Subject: Re: computability of higher homotopy groups Date: Mon, 17 Apr 1995 14:58:49 GMT In the recent thread about computability of higher homotopy groups, nobody seems to have mentioned David Anick's article in the Annals of Math, sometime in the mid 80s, called something like "Computing homotopy groups is #P hard". I don't remember the article too well, but he proves that computing just the rank of the higher homotopy groups of a finite complex is #P hard. This means, I think, that it is at least as hard as every #P problem, in the sense that a polynomial time solution of it would imply a polynomial time solution of every #P problem. I can't remember what #P is exactly--it is harder than NP (conjecturally) and is somewhat similar. Note that he does not prove computability of ranks of homotopy groups is actually in #P--it might be even harder. Of course, you need to get all the definitions straight to really make sense of this. In particular, polynomial time has to be defined in terms of the size of some inputs. I think the inputs come from the way the cells are attached, or something like that. I was actually David's student--he is now about to graduate from medical school! Mark Hovey hovey@math.mit.edu