Topological invariants of classification problems

DOI10.1016/0304-3975(90)90043-HzbMath0693.68024MaRDI QIDQ908698

Lothar Budach

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

branching programsclassification problemsmeasure of complexity

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A topological approach to evasiveness
• Information storage and retrieval systems: Mathematical foundations
• Relationships between nondeterministic and deterministic tape complexities
• Nonuniform complexity classes, decision graphs and homological properties of posets
• Combinatorics and commutative algebra