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