scientific article; zbMATH DE number 139608

MaRDI QIDQ4029586zbMATH OpenFDO

Authors Lothar Budach

Publication date 28 March 1993

zbMATH Keywords

classificationclassifying graphsclassifying treescoloured posetsEuler-Poincaré characteristic

Mathematics Subject Classification ID

Database theory (68P15) Analysis of algorithms and problem complexity (68Q25)

Review text

[For the entire collection see Zbl 0745.00057.] One of the most interesting and outstanding problems in theoretical computer science is the determination of the ``small size Size(C) of certain classification problems \(C\). Though also the determination of Size\((C)\) is not easy, it can be done in certain cases. Some results concerning these questions are presented. The detailed proofs of these results can be read in \textit{L. Budach} [Klassificationsprobleme und das Verhältnis von deterministischer zu nichtdeterministischer Raumkomplexität, Seminarbericht Nr. 68, Sektion Mathematik der Humboldt-Universität, 1-64 (1985; Zbl 0569.68039)].

Recommendations

• Computational complexity of problems in classification according to a relation matrix
• Classifying the computational complexity of problems
• scientific article; zbMATH DE number 1107550
• Topological invariants of classification problems
• Classification and complexity of problems.

Cited in

(7)

• Computational complexity of problems in classification according to a relation matrix
• Classification of binary vectors by stochastic complexity.
• Classification and complexity of problems.
• Classification from a Computable Viewpoint
• scientific article; zbMATH DE number 4020249 (Why is no real title available?)
• Unsolvability Cores in Classification Problems
• Topological invariants of classification problems

This page was built for publication:

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