It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard?
Given an NFA and a natural number $n$, determine if there exists a word of length $n$ that is rejected by the NFA.
At first I thought that it is possible to prove this is NP-Hard by reducing the problem of checking if every word is accepted by an NFA to it, by checking every word length until hitting an upper bound. but according to Yuval Filmus in this question, the upper bound is exponential in the number of states of the NFA, so this reduction does not work.
Is there a valid reduction from a NP-Hard problem, or is this problem solvable in polynomial time?