다항 시간
From Wikipedia, the free encyclopedia
다항 시간(多項時間)은 어떠한 문제를 계산하는 데에 걸리는 시간 m(n)이 문제의 크기 n의 다항식 함수보다 크지 않은 것을 가리킨다.
대문자 O 표기법을 사용하면 m(n) = O(nk)이 된다. 여기서 k는 문제에 따라 다른 상수 값이다.
일반적으로 입력 길이의 다항 시간이 걸리는 경우를 '빠른', 혹은 '다루기 쉬운'(tractable) 경우라고 표현한다. 반대로 다항 시간보다 오래 걸리는 경우를 초다항 시간(超多項時間)으로 부르며, 이 경우는 '다루기 힘든'(intractable) 경우로 표현한다. 초다항 시간에 속하는 예로는 지수 시간이 있다.
결정론적 튜링 기계로 다항 시간에 풀 수 있는 결정 문제의 복잡도 종류는 P이다. 다항 시간에 답이 맞는지 틀린지를 검사할 수 있는 판정 문제의 복잡도 종류는 NP이다. 다시 말하면, NP는 비결정론적 튜링 기계로 다항 시간에 풀 수 있는 판정 문제의 복잡도 종류이다.