Topological invariants of classification problems (Q908698)

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).