Selecting the most representative sample is NP-hard: Need for expert (fuzzy) knowledge
J. Esteban Gamez, Francois P. Modave, Olga M. Kosheleva · 2008
One of the main applications of fuzzy techniques is to formalize the notions of "typical", "representative", etc. The main idea behind fuzzy techniques is that they formalize expert knowledge expressed by words from natural language. In this paper, we show that if we do not use this knowledge, i.e., if we only use the data, then selecting the most representative sample becomes a computationally difficult (NP-hard) problem. Thus, the need to find such samples in reasonable time justifies the use of fuzzy techniques.