정의

A decision problem is in P, the class of polynomial-time problems, if it can be solved by a deterministic Turing machine in polynomial time in terms of the size of its input. That is, a decision problem is in P if there is a deterministic Turing machine T that solves the decision problem and a polynomial p(n) such that for all integers n, T halts in a final state after no more than p(n) transitions whenever the input to T is a string of length n. A decision problem is in NP, the class of nondeterministic polynomial-time problems, if it can be solved by a nondeterministic Turing machine in polynomial time in terms of the size of its input. That is, a decision problem is in NP if there is a nondeterministic Turing machine T that solves the problem and a polynomial p(n) such that for all integers n, T halts for every choice of transitions after no more than p(n) transitions whenever the input to T is a string of length n.

• P
• Class of Polynomial-time problem
• 다항: Polynomial
• 결정적 튜링 기계가 입력의 크기에 관한 다항식으로 표현된 시간 내에 풀 수 있는 결정 문제들.
• $$O(n), O(n^2), O(n^3), ...$$.

어떤 결정 문제를 푸는 결정적 튜링 기계 $$T$$가 있다고 하자.

그리고 $$p(n)$$이 $$p(n) = an^m + bn^{m-1} + ...$$ 형태의 다항식이라 하자.

입력의 길이가 $$n$$일 때, $$T$$가 $$p(n)$$ 횟수 이내의 전이를 거친 후 최종 상태에서 정지한다면 그 결정 문제는 $$P$$에 속한다.

• NP
• Class of Nondeterministic Polynomial-time problem
• 비결정적 다항: Nondeterministic Polynomial
• 결정적 튜링 기계가 입력의 크기에 대한 다항식 시간 내에 풀 수 있는 결정 문제들.

어떤 결정 문제를 푸는 비결정적 튜링 기계 $$T$$가 있다고 하자.

입력의 길이가 $$n$$일 때, $$T$$가 $$p(n)$$ 횟수 이내의 전이 후 최종 상태에서 전이한다면 그 결정 문제는 $$NP$$에 속한다.

참고문헌

• Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등 저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일