Document classification, indexing and abstracting may be inherently difficult problems
Aviezri S. Fraenkel · 1981
The main features of document indexing are abstracted. It is shown that the easy part of indexing, namely the question whether there is a bounded number of descriptors for indexing a document is NP-complete. Thus even the most efficient algorithm for exact indexing is not, at least at the present time, bounded by a polynomial-time function.