Where the Really Hard Problems Went
Computer scientist Daniël van den Berg demonstrates that difficult problems can appear in unexpected places.
Not all computer problems are equally difficult. In his research, Van den Berg and his fellow researchers searched for the very hardest problems within a class. They found these problems in an unexpected place: among the very easiest problems.
The research was conducted using computer simulations and runtime.
Van den Berg and his colleagues hope to eventually demonstrate what these most difficult problems look like and how they can be made easier. For example, could the Dutch Railways (NS) timetable be simplified by adding or removing a few kilometers of track?
More information on the thesis
