Turing Machine

튜링 기계(영어: Turing machine)는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다.

Polynomial time

• 선형 시간: O(n)
• 제곱 시간: O(n²)
• 세제곱 시간: O(n³)

P(Polynomial)

deterministic하게 Polynomial time에 풀 수 있는 문제들의 클래스

• deterministic한 튜링머신으로 polynomial time안에 풀 수 있는 문제들

• deterministic:  어떤 특정한 입력이 들어오면 언제나 똑같은 과정을 거쳐서 언제나 똑같은 결과를 내놓는 알고리즘 

NP(nondeterministic polynomial)

nondeterministic하게 polynomial time에 풀 수 있는 문제들의 클래스
(여러 컴퓨터로 병렬처리를 해야 polynomial time안에 풀 수 있음)

• nondeterministic한 튜링머신으로 polynomial time안에 풀 수 있는 문제들
  (비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다.)

• nondeterministic: 동일한 입력이 주어지더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘

• nondeterministic time: 돌고 돌아서 accept할 수도 있고 조금만 가다가 accept할 수도 있는데 이런 시간들 중 제일 짧은 시간

(특징) output이 정답인지 확인하는 시간이 polynomial time이다.

np complete

np에 속하는 문제들 중 제일 어려운 문제

(knapsack problem)

• 다항 시간에 풀기 어려운 문제