in reply to Multitoken word chains (was The Threeve Game) in thread The Threeve Game
FYI: The problem of finding the longest "chain" is NPcomplete, even in the case of just 2word phrases, as can be seen from a reduction from the longest path problem in directed graphs.
Each single word is a vertex, and there is an edge from word A to word B if "A B" is a valid 2word phrase. A path in the graph corresponds to a "chain" of valid 2word phrases in this game, and we want to find the longest one.
Re^2: Multitoken word chains (was The Threeve Game) by Limbic~Region (Chancellor) on Feb 11, 2010 at 15:46 UTC 
blokhead,
FYI: The problem of finding the longest "chain" is NPcomplete
Yes, I know which is why I said "Oh, I am pretty sure there is a fairly well known computer science problem hidden within so heuristics solutions are likely necessary." See for instance, Not Quite Longest Path Problem. I am really not interested in someone finding the longest path but someone who can find a long path that is longer than everyone else and examine their heuristic solution.
 [reply] 
