Re: What complexity class is 6 Degrees of Kevin Bacon?

Wow! I actually have two different problems I'd given up on that are
both isomorphic to the Kevin Bacon game. Thanks a lot! I might
actually be able to release some really cool utilities soon... just
have to dig up that source code if I haven't already deleted it.
Thanks again!

tchow@xxxxxxxxxxxxx wrote:
In article <1155045025.821444.251400@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
D. C. <enharmonix@xxxxxxxxx> wrote:
My Kevin Bacon Solver's goal is: given the record of any actor, find a
path to Kevin Bacon in 6 steps or less (or tell me if no such path exists).

This can be computed in polynomial time using the Floyd-Warshall algorithm.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

.