What complexity class is 6 Degrees of Kevin Bacon?

Bear with me, but I noticed the 6 Degrees of Kevin Bacon game bears a
/little/ resemblance to the Traveling Salesman Problem.

Suppose I download everything off IMDB and use it to create a list of
actors, and for each actor's entry in the list, I store a list of
references to other actors that that actor has been in a movie with.
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).

In case you haven't figured it out yet, I'm not /really/ trying to
solve this game, it is just isomorphic to another class of problems I
am interested in solving. I don't mind an exponential time solution,
but I don't want an exponential /resources/ solution (building an index
that solves it in P takes an exponential amount of time and space to
build!). Specifically, I would like to be able to solve this in NP (I
doubt a faster solution exists) -- there are good solvers so NP would
be acceptable. PSPACE is not.

Does this sound to anybody like it could be reduced to SAT or TSP? Or
does it maybe belong to some other complexity class? (Or is this just
an elementary complexity question and what I really need is a reference
to a good book?)

Thanks in advance for your help.

.

Relevant Pages