Constructing a NFA that accept complement of language L of another NFA
Is there a general way to do it? The answer is yes: one way to do it is to find a DFA that accepts $L$ (for example with the powerset construction), make it complete (by adding a sink state), and swap final states and non-final states. The automaton is deterministic, but it is a special case of non deterministic.
Is there a polynomial time way to do it? I don't know, since the construction above can be exponential time in the number of states (because of the powerset construction).