The Noncommutative Frobenius Problem is Solved!

Now how am I going to stay awake at night??

here

Consider the famous "Chicken McNuggets problem": if Chicken McNuggets are sold at McDonald's only in boxes of 6, 9, or 20 McNuggets, what's the largest number of McNuggets you can't buy at McDonald's? The answer happens to be my favorite number, 43. (Why it is my favorite is a story that will have to wait for another day.) Notice that you can buy any number of McNuggets greater than 43.

For example, 44 = 4*6 + 1*20, 45 = 5*9,46 = 1*6 + 2*20, 47 = 3*6 + 1*9 + 1*20,48 = 8*6,49 = 1*9 + 2*20, and any number greater than 49 can be obtained by adding an appropriate multiple of 6 to these.In general, you're given a set S of integers, and you want to know the largest number that cannot be expressed as a non-negative integer linear combination of the elements of S. This is called the Frobenius number because Frobenius is supposed to have mentioned it often during his lectures.

...

Unfortunately, the general problem was proved NP-hard (under Turing reductions) by Ramirez Alfonsin in 1996. Roughly speaking, this means the problem is at least as hard as many classical problems for which we still have no efficient solution, such as the traveling salesman problem.

About 6 years ago, I suggested generalizing this problem from numbers to strings of symbols (sometimes called "words"). This kind of generalization is a typical activity in mathematics and theoretical computer science. You take a well-studied problem over one kind of domain, and see how the problem translates in another. The classical Frobenius problem dealt with positive integers, so we'll replace them with strings. Now S will be a set of strings.
...