Stephen P. King (stephenk1@home.com)
Wed, 28 Apr 1999 08:42:45 -0400
Dear Peter,
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,
> though).
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.
>
> Peter
> --
> ------------
> P.M.Hines max003@bangor.ac.uk
Kindest regards,
Stephen
This archive was generated by hypermail 2.0b3 on Sun Oct 17 1999 - 22:31:52 JST