DTM과 NDTM이 recognize하는 language는 완전히 동일합니다. 즉 computing power는 같습니다. 그러나 DTM에서 polynomial time에 풀 수 있는 문제(set P)가 NDTM에서 polynomial time에 풀 수 있는 문제 (set NP)와 같은지 아닌지는 아무도 모릅니다. 이게 P=NP problem이구요. 말씀하신대로 DFA도 NFA와 equivalent합니다. 그렇지만 DPA는 NDPA보다 computing power가 더 작구요.