Given 60fps games, with 5 minutes of play, and 8 NES buttons, it seems reasonable to search through just under 4,608,000 possible plays to find the shortest run!
5 mins * 60 fps * 2^8 button possibilities = 4,608,000 button possibility frames = 4,608,000 possible plays
5 mins * 60 fps * 2^8 button possibilities = 4,608,000 button possibility frames = 4,608,000 possible plays