scientific article; zbMATH DE number 1107550
It is not my aim to guide readers to the leading edge of research in complexity theory or in the complexity of classification problems. Rather, I offer a tutorial on basic concepts of complexity theory (e.g., problem, algorithm, complexity class, NP-completeness), and I use them to analyze the complexities of two representative classification problems. Section 2 introduces the basic constituents of complexity theory: problems, algorithms, and computing machines. Section 3 concerns the complexity of algorithms: measuring algorithmic complexity according to computational resources, describing asymptotic behavior of resource consumption, using bounds on asymptotic behavior to determine algorithmic efficiency or optimality. Section 4 uses these concepts to analyze the complexities of algorithms that construct nonhierarchical classifications (i.e., partitions of a set) or hierarchical classifications (i.e., dendrograms or ultrametric trees). Section 5 describes problem complexity classes that are based on two standard models of computation and defines the well-known classes of NP-complete and NP-hard problems. Section 6 uses these concepts to discuss the complexities of problems on nonhierarchical and hierarchical classifications. Although some classificatory problems are solvable by efficient algorithms, most are computationally so difficult that they are NP-complete or NP-hard. For readers wishing more information on complexity theory, or the complexities of classification, I conclude Sections 2-6 with bibliographic remarks. For the entire collection see [Zbl 0836.00014].
- Complexity of classification problems
- Classification of binary vectors by stochastic complexity.
- Clustering on trees
- Taxicab correspondence analysis
- A comparison of heuristic procedures for minimum within-cluster sums of squares partitioning
- Distinguishing and classifying from n-ary properties
- Extremes in the Complexity of Computing Metric Distances Between Partitions
- Classification from a Computable Viewpoint
- Computer-Aided complexity classification of combinational problems
- scientific article; zbMATH DE number 139608 (Why is no real title available?)
- scientific article; zbMATH DE number 622666 (Why is no real title available?)
- Recognition method of algorithms classes on the basis of asymptotics for the elasticity of complexity functions
- Elements of classification. Combinatorial aspects and algorithms
- Computational complexity of two problems of cognitive data analysis
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 Q4373479)