## Road Coloring Problem Solved 202

Posted
by
kdawson

from the hard-but-not-complicated dept.

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."*
## The writeup is misleading (Score:5, Informative)

## Re: (Score:2)

Where one works isn't always a sign of ones abilities.

## Irrelevant (Score:2)

He's been teaching at the Bar-Ilan university since 1995.

The summary makes it sound like he was a security guard doing math in his spare time.

## The parent is misleading (Score:4, Informative)

'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: (Score:3, Informative)

## Applications? (Score:4, Interesting)

## Re:Applications? (Score:5, Informative)

## Re: (Score:2)

## Re: (Score:2)

Basically, if you called me up on the phone I could give you directions without knowing where you started from:

1. Take the blue road.

2. Take the red road.

3. Take the next red road.

Now, if you started in the node next to mine, this is not an efficient route - but it sure does simplify directions. I could see how it could also help routing if one of the paths is damaged... if you get to a broken "road", just start over from the first instruction and yo

## Re: (Score:2)

## Re: (Score:2)

. Again, if there are a finite number of paths, there must be a finite number of routes (combinations of paths). So just try them all.

Again, I'll refer you to the Wikipedia article. It's not quite that simplistic. The real meat of the (is it still a conjecture?) is:

So it describes the exact conditions that a system must meet in order for this behavior to be described. Not just any collection of connected points will have such a solution - so no, it's not obvious :)

Then again, I'm in waaaaay over my head here - I am but a bachelors

## Re: (Score:2)

## Re: (Score:2)

The whole point of having a GPS unit is so that you know your starting location.

If the result apply to 3D spaces, I would say it'll probably have some implication for biotech or nanotech assembley as guidance clues for stem cells or nannites. I'd say it's more likely to be nanotech though, since we already have better ways to guide cells.

## Classic maze solution (Score:2)

## It's a theorem (Score:4, Insightful)

It's a theorem which states that if a graph is strongly connected and aperiodic, then there exists a road coloring. It was conjectured by Weiss and proven by Trahtman 30 years later, which is what the article is about. A graph that is periodic may still have a road coloring, but that's not the scope of the theorem.

Most roads are strongly connected but periodic (not aperiodic), in the sense that you can drive around a block in 4 segments, and drive around 2 blocks in 6. The period in this case is 2. You can't guarantee a computer network to be aperiodic either. These graphs may still have a road coloring, but the theorem doesn't apply. Therefore, this theorem has little application in practice.

I haven't read the paper, but there are generally two ways to prove the theorem: (1) show a coloring algorithm that makes only the assumptions of strong connectivity and aperiodicity, or (2) show the contraposition, that if there is no road coloring, then it implies either the graph is not strongly connected or there is period. Only (1) is useful in practice because you have a method to generate road coloring and instructions to reach all vertices, but it's harder to verify that (1) is correct. (2) is not very useful because although you have a proof, but you don't end up with an algorithm that generates road coloring.

In practice, algorithms get things done. Proofs are only certificates.

## Bad timing. (Score:5, Funny)

## Re: (Score:2)

Unfortunately for him, a cheap, safe, mass-market flying car was announced an hour later.Fortunately for him, the massive new air traffic control industry needed a route-finding algorithm.

## Re: (Score:2)

Unfortunately for him, a cheap, safe, mass-market flying car was announced an hour later.This one?

http://www.pal-v.com/ [pal-v.com]

## Link to the solution (Score:5, Informative)

## wikipedia (Score:5, Informative)

## Re: (Score:2, Informative)

## Re: (Score:2, Informative)

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: (Score:2)

iscase sensitive, but a redirect page exists from "Road Coloring Conjecture" to "Road coloring conjecture". But, yeah, the slash thing is more pertinent here (although I think you meant trailing slashes, not leading ones).## Re:wikipedia (Score:5, Informative)

## Re:wikipedia (Score:5, Informative)

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 fromthat 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: (Score:2)

You would keep repeating them until you ended up at the intersection

named"Red-Blue-Blue". That is the address, after all.## Re: (Score:2)

## A Subquadratic Algorithm for Road Coloring (Score:5, Informative)

## Old news? (Score:5, Insightful)

2. Apparently his proof was published last September. It's "news" because it's just now hitting the semi-mainstream press. You people fail at nerddom.

## Re: (Score:3, Funny)

Apparently his proof was published last September. It's "news" because it's just now hitting the semi-mainstream press. You people fail at nerddom.No, they're just applying the normal slashdot skepticism. The guy was a security guard for crying out loud. And he's old. Really old. No way he could have used his brain to solve something involving math. Besides, he's probably only trying to get seed money so he can start a pyramid scheme selling perpertual motion.

## Re: (Score:2)

## Re: (Score:2, Insightful)

## Re: (Score:3, Funny)

## Re: (Score:2)

In other words, the Romans were right, and "All roads lead to Rome"?

## Actually (Score:3, Interesting)

## Re: (Score:2)

## Re: (Score:2)

## Re:Actually (Score:5, Funny)

Where's my PEDANTIC:-1 option?

## Sign of a true Genius. (Score:5, Insightful)

The man

isa True Genius. Insight to all of out out there, that is the proper way of thinking.## Re:Sign of a true Genius. (Score:4, Funny)

isa True Genius.Today, we salute you, Mr. former-nightwatchman-turned-mathmetician!

## Re: (Score:2)

Of course, his acchievements prove that he is not a loser like those bastards who can't even RTFA before posting.

## HIRED! (Score:3, Funny)

## Slashdottings in real life? (Score:2)

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. Experts say the proposition could have real-life applications in mapping and computer science.

If a thousand people arrive at a shopping mall, at the same time, isn't that called a flash mob [wikipedia.org]? Then I guess this conjecture has already been solved online, and it is called Slashdot.

## What about the cyclical traps? (Score:2)

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

I agree that specific solution works, but what about the general cases of the other 3 length permutations of 'r' and 'b'...Try 'bbb' and 'rrr' from any node, and you'll find 3 terminal nodes for each path.

I don't think that matters. As I understood it (and I could be wrong), the theorem is that for any node you can find a set of directions that will lead you to it from any other arbitrary node. It doesn't state that all possible direction permutations will lead you to a unique node, just that there's one that will. So 'bbb' and 'rrr' are just never going to be used as directions.

## scratch that (Score:2)

From actually trying the graph out, I actually don't even see anything that's different with 'bbb' or 'brr'. 'bbb' is an instruction set that will lead you to node 8 and 'brr' will lead you to the yellow node. I also misread what the original poster was saying. I think you do have to follow the whole direction set if you don't know where you're going (and you can figure out that you're there if the next time you follow 3 directions leads you into a loop back where you started), but nothing should stop yo

## Re: (Score:2)

## Washington - RNC ??? (Score:3, Funny)

"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."## Re: (Score:2)

## so.. (Score:2, Funny)

## What is road-coloring (and why we should care) (Score:5, Interesting)

## I knew it! (Score:5, Funny)

## and the evil professor says ... (Score:3, Funny)

Show your work.

## Didn't AAA solve this long ago? (Score:2, Funny)

Have mathematicians scraped the bottom of the barrel for unsolved puzzles? Oh, damn. I think I just created something for mathematicians to ponder for the next few decades...

## In related news .... (Score:4, Funny)

## Gems (Score:2)

## Re:XKCD (Score:5, Informative)

## Re: (Score:3, Informative)

## Re: (Score:2)

You know what that means right? We could finally make a computer play a perfect game of tetris!

## Re: (Score:3, Informative)

anypointanywhereas 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: (Score:3, Funny)

wait, ohio to cleveland?

## Re: (Score:2)

endup in Pittsburgh unless you finally tire of traveling, but you may pass through Pittsburgh many times on your way to Cleveland. Hell, you might pass though Lima, Peru on your way to Cleveland, Ohio. For that matter, you might pass though Cleveland, Ohio itself several times before you complete the trip according to the instructions.## Re: (Score:2)

Yes, and M.C. Escher-style.

## Re: (Score:2)

this guarantees you'll never *end* up in pittsuburgh.I have a question regarding this. It seems to me that you *could* end up in Pittsburgh, assuming following the pattern brings you there and that's were you decide to stop. I guess what I'm trying to get at is this: if following the pattern "red, red, blue" will eventually, at some point, bring be to Cleveland, that does seem useful. But does this problem address the question of, "how do I know when I've reached Cleveland?"

Within this method where a

## Re:Yeah, yeah, First Post, but... (Score:4, Insightful)

## Re: (Score:2)

## Re: (Score:2)

(having worked in Hoboken and now living in Cleveland)

## Re: (Score:3, Funny)

What airlines have

youbeen using lately? Not the ones I fly, certainly.## Re:Night Watchman? (Score:5, Funny)

## Re: (Score:2, Funny)

## Re: (Score:2, Funny)

In Soviet Russia they say that because Americans were so poor mathematicians, they had to invent the computer...I hear that Russians are such poor computer scientists, they had to get good at math...

## Re: (Score:2)

-- Calvin, from "Calvin and Hobbes" by Bill Watterson

## Re: (Score:2)

And it can be a lot faster

andmore accurate to optimize with a pencil than with generic optimization algorithm.## Re:Night Watchman? (Score:4, Funny)

## HE'S NOT A WATCHMAN (Score:5, Informative)

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: (Score:3, Interesting)

http://developers.slashdot.org/article.pl?sid=08/03/04/2348257 [slashdot.org]

## Re: (Score:2)

## Re:Night Watchman? (Score:4, Interesting)

wasa night watchman, but it looks to me like he's a professor now...## Re: (Score:2, Flamebait)

According to Wikipedia [wikipedia.org], he is a mathematician at Bar-Ilan University in Israel. Here is his homepage [biu.ac.il] hosted by the university. Maybe he was a night watchman, but it looks to me like he's a professor now...No surprise. I mean, have you tried pronouncing his name? It sounds almost exactly like "Tractorman". That's a hell of an advantage in life. Just imagine if everywhere you went, people introduced you as "Tractorman" and you introduced yourself saying, "Pleased to meet you, I'm

## I thought they were bionic (Score:2)

## Re:Night Watchman? (Score:4, Informative)

## Re: (Score:2)

## Re: (Score:2, Informative)

IANAM, but I believe he solved the problem, not the solution.

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2, Funny)

Fixed it for you.

## Re: (Score:2)

Goddamn, this thread is getting tedious.

## Re: (Score:2)

And in my experience, you mainly see that America-only stuff in the public sector(and even then, not too often). The business world tends to know better.

## Re: (Score:2)

We don't hear about murders, cheaters in professional sports, or obscure accomplishments unless they are of interest to the local region/nation/community.

If the man was French, you would see it all over the French news, but he was not. So it's just a little footnote on non-Israeli and non-Russian news. Of course it is important to scientific, engineering and mathematic community so it's big news over there.

It's a mat

## Re: (Score:2, Insightful)

## Re: (Score:3, Informative)

However, the article ALSO says he's been teaching mathematics at Bar Ilan University since 1995; the university is where he solved t

## Re: (Score:2, Informative)

## Re: (Score:2)

## Re: (Score:2)

## Re:OK, but... (Score:4, Funny)

## Re: (Score:2)

How many paths must a man walk down before you can call him a man?Well, unfortunately for all us Free Worlders out there, that path is apparently a Red one.

## Re: (Score:2)

The question implies you are not a man if you don't walk down any paths.

## Re: (Score:2)

Wikipedia has a relatively clear example of the problemI think Wikipedia

isa relatively clear example of the problem.