No label defined (Q4373479)

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