Here's the problem. Every word in a dictionary is defined by a set of other words. For example "cat" may be defined as "small mammal with fur". Can we choose a set of 'base' or 'prime' words such that every word in the dictionary is definable in terms of these words? There will be no unique solution since there will be some loops such as:
bricks = what walls are made of
wall = a structure made of bricks
so we could select either of these words to be a "prime" word.
Is there a known algorithm that, given a dictionary, could find a set of prime words. And is there an algorithm that could find the smallest set of prime words? Is this a known problem? What is it's complexity? What would happen if you applied this algorithm to an actual dictionary?
A dictionary with definitions is a directed graph where each word refers to the words used to define it (there should be no self references). We then try to find a maximal subgraph of this graph with the same vertices that has no cycles.
Finding this set is called the "minimum feedback arc set problem" and it is NP-complete:
https://stackoverflow.com/questions/6284469/how-to-remove-cycles-in-an-unweighted-directed-graph-such-that-the-number-of-ed
The prime words are then those which had an outgoing edge removed or had no outgoing edges to begin with.
Edit: The problem might even be "a bit harder", for to get the minimum number of prime words, we would have to try to break as many cycles as possible with edges removed from as few vertices as possible. However, since bruteforce works for this we still get NP complexity.