**Stephen P. King** (*stephenk1@home.com*)

*Wed, 28 Apr 1999 08:42:45 -0400*

**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Stephen P. King: "[time 262] Is thinking more like a thunderstorm or like a calculation?"**Previous message:**Stephen P. King: "[time 260] Re: Other Minds"

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

**Next message:**Stephen P. King: "[time 262] Is thinking more like a thunderstorm or like a calculation?"**Previous message:**Stephen P. King: "[time 260] Re: Other Minds"

*
This archive was generated by hypermail 2.0b3
on Sun Oct 17 1999 - 22:31:52 JST
*