Let L be the language which recognizes polynomials in Z[x] (polynomials with integer coefficients) which have an integer solution. We need to show that L is in NP.

I am trying to come with up a witness with polynomial size but I can't. Checking every integer 0, 1, -1, 2, -2.... wouldn't work.