The extraction of a minimum set of semantic primitives from a monolingual dictionary is NP-complete
David P. Dailey · Computational Linguistics · 1986
Within the last 15 years, a variety of unsolved problems of interest primarily to operations researchers, computer scientists, and mathematicians have been demonstrated to be equivalent in the sense that a solution to any of them would yield a solution to all of them. This class of problems, known as NP-complete, contains many long-standing problems of scheduling, routing, and resource allocation. This note contains a demonstration that a problem of interest to applied linguistics also belongs to this class - namely, the process of extracting a minimum set of semantic primitives from a monolingual dictionary is NP-complete, implying that the task is currently computationally insoluble.