On the complexity of learning strings and sequences (Q688167)

It is shown that strings (sequences) are not learnable by strings (sequences) in the distribution-free (pac-) learning model proposed by Valiant. The key role in the argument is played by the results on the complexity of consistent superstring and consistent supersequence problems. The consistent superstring problem is defined as follows: given two collections of strings, called positive examples and negative examples, decide whether there exists a string containing all positive examples as substrings and no negative example as a substring. The consisting supersequence problem is defined similarly. Both problems are proved to be NP-complete.