Stephen P. King (firstname.lastname@example.org)
Wed, 28 Apr 1999 08:42:45 -0400
Thank you for the information. ;) Would you happen to know a reference?
Peter Hines wrote:
> Stephen Paul King wrote:
> > Hi all,
> > Is the problem of classifying 3-manifolds NP-Complete
> > computationally?
> > Thanks,
> > Stephen
> > [Moderator's note: when I last checked, nobody knew if there was any
> > algorithm to classify compact 3-manifolds. But I suppose someone could
> > still have shown the problem is *at least* NP-complete, i.e., no easier.
> > - jb]
> Hi, Stephen.
> Aren't 3-manifolds equivalent to knot / link complements? If so, then the
> equivalence problem for these has been solved, which would imply a
> classification of 3-manifolds (the procedure is -much- harder than NP,
As far as I have read, e.g. from Ian Stewart's books...
> I vaguely remember that the problem for the next dimension up (4-manifolds)
> is Turing machine equivalent, so no classification procedure can exist
> (although this was a long time ago - I'm not sure about that).
Interesting! ;) Might we think of the solutions of general relativity
as being subject to such?
> Best wishes, anyway.
> P.M.Hines email@example.com
This archive was generated by hypermail 2.0b3 on Sun Oct 17 1999 - 22:31:52 JST