A Deliberate Day
Earlier this week, after three days of trying, I proved an interesting theorem. I was studying a certain type of scheduling problem in graphs. I was finally able to prove that without lots of knowledge about the graph no algorithm can solve the problem fast.
This morning I set out to extend this result. I wanted to know what happens if you have more knowledge. After about an hour, I had a partial answer: If the graph is small in a certain way there is an algorithm that can solve the problem fast — I know this because I found it.
Unfortunately, for more general structures I couldn’t make the math play nice. I had a hazy intuition, but attempt after attempt to make it concrete failed. I couldn’t hold the pieces straight in my head. (See here for more on the style of problem I’m talking about here.)
After another 3 – 4 hours I had to stop for the day.
