On the Complexity of Clustering Problems
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
The class of discrete optimization problems may be partitioned into two subclasses PS and P?. PS is the subclass of problems which are known to be polynomial solvable. P? is the subclass of problems for which it is not yet known whether an algorithm exists which is polynomial bounded. The subclass P? contains the class NPC of NP-complete discrete optimization problems. NPC has the important property that if only one member of NPC can be shown to be polynomial solvable all members of NPC as well as a large number of other combinatorial problems are polynomial solvable. However, it seems to be very unlikely that all NP-complete problems are polynomial solvable.