Hi, is there an algorithm that determines if a given simplicial complex is a.) a manifold b.) a smooth manifold c.) homotopy equivalent to a manifold d.) a real algebraic variety
?
Hi, is there an algorithm that determines if a given simplicial complex is a.) a manifold b.) a smooth manifold c.) homotopy equivalent to a manifold d.) a real algebraic variety ? 


A simplicial complex is a manifold if the links of all vertices are simplicial spheres. Recognizing the $n$sphere is easy for $n=1, 2$, tractable for $n=3$ (the RubinsteinThompson algorithm and refinements thereof. I believe it is still exponential time), and undecidable for $n\geq 5$ by a result of Novikov  see http://www.inf.ethz.ch/personal/wagneru/Manuscripts/e4hard.pdf and references therein. Don't know about $n=4.$ As for "real algebraic variety", every manifold is homotopy equivalent to a real algebraic variety (this is Nash's famous theorem), and every manifold of dimension less than 10 is homeomorphic to a real algebraic variety (see http://www.ams.org/journals/bull/19778302/S000299041977143073/S000299041977143073.pdf), so in those dimensions your last question collapses to your first question. EDIT As pointed out by @Lennart Meier in his comment, in fact, every smooth manifold is homeomorphic to a real algebraic variety. 


There is the idea of a simplicial manifold, which works by checking that the complex is pure (all facets of the same dimension) and that each codimension 1 face is included in the correct number of facets. Beyond this answer to your question a), I believe b) and d) to be potentially really difficult. It would seem to me that almost no simplicial complexes are in themselves smooth (unless you give an explicit embedding, in which case you need to check smoothness for each face separately, or something like that), but that all simplicial manifolds can be deformed into a smooth manifold. As for c), it seems to reconnect to the criterion for a), but it is not clear to me whether algorithmics exist. You might want to check out the work by Benjamin Burton. 


(b) When does a PL manifold have a smooth structure? I believe that this is computable. Smoothing theory, closely related to the HirschSmale immersion theory (an hprinciple), identifies the set of smooth structures on a PL manifold with the set vector bundles that are reasonable candidates for the tangent bundle in the sense that they are reductions of structure group of the PL tangent bundle. The theory of principal bundles reduces to homotopy theory. The set of homotopy classes of maps from a finite complex to a finite complex with abelian fundamental group and the induced maps between such sets are computable, but it is rarely implemented. 

