Forgot your password?
typodupeerror
Math Science

Road Coloring Problem Solved 202

Posted by kdawson
from the hard-but-not-complicated dept.
ArieKremen writes "Israeli Avraham Trakhtman, a Russian immigrant mathematician who had been employed as a night watchman, has solved the Road Coloring problem. First posed in 1970 by Benjamin Weiss and Roy Adler, the problem posits that given a finite number of roads, one should be able to draw a map, coded in various colors, that leads to a certain destination regardless of the point of origin. The 63-year-old Trakhtman jotted down the solution in pencil in 8 pages. The problem has real-world implementation in message and traffic routing."
This discussion has been archived. No new comments can be posted.

Road Coloring Problem Solved

Comments Filter:
  • by karl marx is my hero (1222496) on Friday March 21, 2008 @09:42AM (#22818422)
    The guy is actually a mathematician who had to work as a security guard right after he immigrated to Israel, which is common for most immigrants. This guy had lots of formal training solving equations like this.
  • Re:XKCD (Score:5, Informative)

    by Anonymous Coward on Friday March 21, 2008 @09:47AM (#22818498)
    No, today's XKCD is about the traveling salesman problem. They are very different.
  • Link to the solution (Score:5, Informative)

    by wiredog (43288) on Friday March 21, 2008 @09:51AM (#22818554) Journal
    Since the one in the write-up is borken. Here [arxiv.org] it is.
  • by darthflo (1095225) on Friday March 21, 2008 @09:54AM (#22818584)
    I wouldn't consider myself mathematically literate, but applying the findings of Trakhtman to navigation instructions in the real world would, if I understand the theorem [wikipedia.org] correctly, make finding any point anywhere as easy as "at intersections, follow the pattern red-blue-blue".
    What I don't quite get, is the efficiency of this. The WP example looks like, transferred to the real world, a trip from Ohio to Cleveland may very well go through Indiana and Pittsburgh. Not what I'd consider efficient/fast routing.
  • Re:Night Watchman? (Score:4, Informative)

    by DirePickle (796986) on Friday March 21, 2008 @09:56AM (#22818618)
    He's in Israel, not the US, dude. Save your diatribe for another time.
  • wikipedia (Score:5, Informative)

    by ZiggyM (238243) on Friday March 21, 2008 @09:58AM (#22818638)
    from Wikipedia: In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. http://en.wikipedia.org/wiki/Road_Coloring_Conjecture/ [wikipedia.org]
  • by Frans Faase (648933) on Friday March 21, 2008 @10:03AM (#22818694) Homepage
    Apart from the referenced paper being some months old, the author has an extended paper with an efficient algorithm. See A Subquadratic Algorithm for Road Coloring [arxiv.org].
  • HE'S NOT A WATCHMAN (Score:5, Informative)

    by mcmonkey (96054) on Friday March 21, 2008 @10:15AM (#22818824) Homepage

    If you RTFA (yes, I must be new here) he worked as a night watchman when he first moved to Isreal. He's been working in mathematics for over a decade.

    Originally from Yekaterinburg, Russia, Trahtman was an accomplished mathematician when he came to Israel in 1992, at age 48. But like many immigrants in the wave that followed the breakup of the Soviet Union, he struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995.

    You might as well say the 2002 Nobel prize in economics went to a lieutenant in the army. It's just a minor detail that he was a lieutenant 50 years before winning the prize.

  • Re:wikipedia (Score:5, Informative)

    by Stephan202 (1003355) on Friday March 21, 2008 @10:26AM (#22818948) Homepage
    Drop the trailing slash: http://en.wikipedia.org/wiki/Road_Coloring_Conjecture [wikipedia.org]
  • Re:wikipedia (Score:2, Informative)

    by nherc (530930) on Friday March 21, 2008 @10:34AM (#22819048) Journal
    Oddly Wikipedia directory/article URL listings seem case sensitive and the given one pointing at 'Road_Coloring_Conjecture' does not work, but 'Road_coloring_conjecture' does. The correct Wikipedia link to the Road Coloring Conjecture page is http://en.wikipedia.org/wiki/Road_coloring_conjecture [wikipedia.org].
  • Re:wikipedia (Score:5, Informative)

    by Jasin Natael (14968) on Friday March 21, 2008 @10:39AM (#22819120)

    The problem is more constrained than that. Think about it more like this: You're in a town that's been planned very carefully. At any intersection, the possible roads away from that intersection are labeled with colors. I'll assume three colors, and that each intersection has exactly three roads leading away from it (the number of roads that lead into the intersection doesn't matter).

    Your friend tells you that his address is "Red-Blue-Blue". This means that, no matter which intersection you start from, by repeatedly following these directions, you WILL end up at his house.

  • Re:wikipedia (Score:2, Informative)

    by magicchex (898936) <mdanielewicz.gmail@com> on Friday March 21, 2008 @10:45AM (#22819174)
    Actually it is not case sensitive. http://en.wikipedia.org/wiki/Road_coloring_conjecture [wikipedia.org] works just as well as http://en.wikipedia.org/wiki/Road_Coloring_Conjecture [wikipedia.org]

    However, leading slashes break the link, so both http://en.wikipedia.org/wiki/Road_coloring_conjecture/ [wikipedia.org] and http://en.wikipedia.org/wiki/Road_Coloring_Conjecture/ [wikipedia.org] do not work.
  • Re:Night Watchman? (Score:2, Informative)

    by BattleApple (956701) on Friday March 21, 2008 @10:55AM (#22819306)

    He emigrated to Israel where he solved the solution.

    IANAM, but I believe he solved the problem, not the solution.
  • Re:Applications? (Score:5, Informative)

    by MightyYar (622222) on Friday March 21, 2008 @11:05AM (#22819430)
    Egads, please no! This only guarantees that you will arrive at a destination from an arbitrary start point. Even if you could somehow use it for Google directions, your route would be crazy. You could start out next door to your destination and it may take you a day-and-a-half of travel to finally wind up there as you tour all over the city. I can see this being interesting to networking, though. A guaranteed route somewhere from any start point sounds pretty cool, even if a bit inefficient.
  • Re:XKCD (Score:3, Informative)

    by Jawbreaker4Fs (974108) on Friday March 21, 2008 @11:06AM (#22819442)
    Yeah... this would only apply to the XKCD comic if the road coloring problem was NP-complete.
  • Re:Night Watchman? (Score:3, Informative)

    by Sparks23 (412116) * on Friday March 21, 2008 @11:32AM (#22819798)
    Trakhtman is a Russian Jew who immigrated to Israel in 1992 after the breakup of the Soviet Union, and the article says that he had trouble finding work during the influx of refugees. Not because of his background, but because of a sudden unemployment glut. This is why he previously ended up serving as a night watchman, a laborer, a maintenance worker or whatever else he did.

    However, the article ALSO says he's been teaching mathematics at Bar Ilan University since 1995; the university is where he solved the problem.
  • Re:Night Watchman? (Score:2, Informative)

    by bob.appleyard (1030756) on Friday March 21, 2008 @11:48AM (#22820018)
    I know a Polish biochemist who works as a maid over here in the UK. Makes more doing that than doing biochemistry stuff in Poland, so he's happy for the moment and sending the money back. I imagine this will change in a few years.
  • by PDAllen (709106) on Friday March 21, 2008 @04:41PM (#22823518)
    The road colouring problem is not 'an equation'.

    'deterministic automaton' basically means: computer program which doesn't have any form of randomness involved. If you're in this particular state in the program and you do this particular thing then always the same thing happens.

    The road colouring problem amounts to: For any program, I claim that there is one single sequence of actions so that if you do this sequence of actions, from whatever start point, when you finish you will be in a specific state (`target', say) of the program.

    If you take any real normal program, it's `obvious' what to do: for example if you're looking at 'edit' and you want a typed copy of Shakespeare in Times 12pt, you hit backspace as many times as edit can have characters (lots, but it's a finite number) then you go through the menus by keypress and set each style to the correct thing, then you start typing in the works of Shakespeare which eventually gives you the target state. And it doesn't matter if the monitor was off, you know that this method definitely works, whatever state edit was in when you got there, whether it was in the blank just loaded state, or whether it was editing font size in War and Peace, whatever.

    It is not so easy to prove that in fact for any program you can find such a sequence.

    In fact, it isn't even true. A really simple example is the program which every time you press a key changes the screen between red and blue. Now you're supposed to give a sequence of actions - keystrokes - which are guaranteed to end up with the screen blue (target state). But really what the keystrokes are is irrelevant. This program doesn't care if you press 'a' or 'ESC', it just changes screen colour every stroke. So really your sequence of actions comes down to 'press keys however many times'. How many times? Well, if the screen starts red (and remember the monitor is off, so you don't know if that's true) then you'd need to press keys an odd number of times to get it to end up blue. So you have to do that. But then what happens if the screen started blue? It ends up red. This sequence of actions doesn't always reach the target state - and there cannot be any sequence of actions which does.

    So you have to impose a condition to make the result true. In the example I gave, the program has two states and it loops between them. It's a program with exactly one loop, of length two, and the greatest common divisor (GCD) of these loops is of course 2. Basically, having the ability to loop between states like this (or in a loop of length 3, or 4, or whatever) is the only 'obvious' barrier to having a sequence of actions which goes to a target state. So you impose a condition: the GCD of all the loops is 1 (this doesn't mean there are no loops, but the guy proves it means you can find a way out of all the loops). If you don't have that, then you can find automatons (programs) which work like the example and you cannot possibly have the sequence of actions you need. If you do have it, there is no 'obvious' barrier to the sequence of actions existing. And what this paper shows is that there isn't any hidden catch: once you get rid of the 'obvious' barrier then you can find a sequence of actions which definitely puts the program you're looking at into the target state.
  • Re:Huh? (Score:3, Informative)

    by PDAllen (709106) on Saturday March 22, 2008 @06:06AM (#22828052)
    I didn't even mention NP-completeness. Mainly because it has nothing to do with the problem. Are you just slinging buzzwords on a subject you don't understand?

FORTUNE'S FUN FACTS TO KNOW AND TELL: #44 Zebras are colored with dark stripes on a light background.

Working...