Computational complexity of problems in classification according to a relation matrix
type: Item
instance of: scholarly article
title: Computational complexity of problems in classification according to a relation matrix
zbMATH Open document ID: 0605.68028
author: M. M. Gil'burd
author: E. Eh. Sinitsyn
published in: Automation and Remote Control
publication date: 1985-01-01T00:00:00Z
review text: Statements of the problem of classification according to a relation matrix with the use of numerical criteria (functionals) of the connectivity of elements in a subset are discussed. It is proved that, given certain assumptions about the connectivity functional, the corresponding classification problem is NP complete.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 62H30
zbMATH DE Number: 3978377
zbMATH Keywords: connectivity functional
zbMATH Keywords: NP complete
MaRDI profile type: Publication
Recommended article: Q4029586
Recommended article: Complexity of classification problems
Recommended article: Co-NP-completeness of some matrix classification problems
Recommended article: Q4733859
Recommended article: Classifying the computational complexity of problems
Recommended article: Complexity of matrix problems
Recommended article: Some Relations between Classes of Low Computational Complexity
Recommended article: Q4820785
Recommended article: Complexity analysis of algorithms by recognition of their classification properties
description: scientific article; zbMATH DE number 3978377