Is there an efficient algorithm to decide whether the language accepted by one NFA is a superset of the language accepted by another?

Question

Given two nondeterministic finite automata M1 and M2, is there an efficient algorithm to determine whether the language accepted by M1 is a superset of the language accepted by M2?

Answer 1

Not unless P=NP. If you had such an algorithm, you could trivially decide whether two NFAs were isomorphic (just check if A is a superset of B and B is a superset of A), which is a known NP-hard problem. For more details, read this paper. It has a nice discouraging table of complexity results.