how to solve NFA acceptance problem in polynomial time I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires exponential time.

I would appreciate any help, Thanks in advance..
Hint (expanding on David Richerby's hint): As the NFA reads $w$, keep track of the set of states it could be in at any given time.