| [ PhilosophyThought ] in KIDS 글 쓴 이(By): constell (호이~!) 날 짜 (Date): 2000년 2월 21일 월요일 오후 11시 39분 59초 제 목(Title): Re: Q]결정적시스템과 비결정적시스템의 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가 더 작구요. |