The problem (as stated) is not intractable. It may be super-polynomial, but I don't think so. (Just intuition; could be wrong.)