Topological invariants of classification problems

Complexity of computation (including implicit computational complexity) (03D15) Planar graphs; geometric and topological aspects of graph theory (05C10) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Review text

There is a general agreement that problems which are highly complex in any naive sense are also difficult from the computational point of view. It is therefore of great interest to find invariants and invariant structures which measure in some respect the complexity of the given problem. The question which we are going to consider are classification problems, the ``computations are described by questionnaires or, as they are called nowadays, by ``branching programs. The ``complexity of the problem is measured by classical topological invariants (Betti numbers, Euler-Poincaré characteristic) of topological structures (simplicial complexes, topological spaces).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Topological invariants of classification problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908698)