결정 론적 계산과 비 결정적 계산

수업을 이해하려면 P 과 NP, 먼저 계산 모델을 알아야합니다. 따라서이 장에서는 두 가지 중요한 계산 모델에 대해 설명합니다.

결정 론적 계산과 클래스 P

이러한 모델 중 하나는 결정 론적 단일 테이프 튜링 머신입니다. 이 기계는 유한 상태 제어, 읽기-쓰기 헤드 및 무한 시퀀스의 양방향 테이프로 구성됩니다.

다음은 결정 론적 단일 테이프 튜링 머신의 개략도입니다.

결정 론적 튜링 머신을위한 프로그램은 다음 정보를 지정합니다.

알고리즘 분석에서 결정 론적 하나의 테이프 튜링 머신에 의해 다항식 시간에 문제를 해결할 수있는 경우 문제는 P 클래스에 속합니다.

계산 문제를 해결하기위한 또 다른 모델은 비 결정적 튜링 머신 (NDTM)입니다. NDTM의 구조는 DTM과 유사하지만 여기에는 하나의 쓰기 전용 헤드와 관련된 추측 모듈이라는 추가 모듈이 하나 있습니다.

다음은 회로도입니다.

비 결정적 튜링 머신으로 다항식 시간에 문제를 해결할 수있는 경우 문제는 NP 클래스에 속합니다.