March 20, 2008
The Road Coloring Problem Is Solved after 38 Years
Avraham Trahtman, an Israeli immigrant from Russia has solved a 38 year old math problem called the Road Coloring Problem.
The conjecture essentially assumed it’s possible to create a “universal map” that can direct people to arrive at a certain destination, at the same time, regardless of starting point.
Roughly a hundred scientists worked to solve the problem over the years and all failed until Trahtman composed the solution in eight pages.
“The solution is not that complicated. It’s hard, but it is not that complicated,” Trahtman said in heavily accented Hebrew. “Some people think they need to be complicated. I think they need to be nice and simple.”
So, what applications does the solution hold?
“Say you’ve lost an e-mail and you want to get it back — it would be guaranteed,” he said. “Let’s say you are lost in a town you have never been in before and you have to get to a friend’s house and there are no street signs — the directions will work no matter what.”
Leave a Reply
