더 자세한 내용으로 들어가기 전에 먼저 몇 가지 용어를 정의하겠습니다.
• 다항시간 알고리즘(polynomial time algorithm): 알고리즘의 시간 복잡도가 O(nk)이고 k가 상수라면 이 알고리즘을 다항시간 알고리즘이라고 부릅니다.
• 증명서(certificate): 알고리즘을 반복적으로 개선하는 과정에서 생성되는 후보 해결책을 증명서라고 부릅니다. 특정한 문제를 반복해서 풀어 나가면 일련의 증명서들이 생성됩니다. 이 증명서들이 점차 어떤 특정한 방향으로 수렴한다면, 새롭게 생성된 증명서가 이전에 만들어진 것보다 더 낫다고 판단할 수 있습니다. 이때 증명서가 문제의 요구조건을 만족하는 지점에 다다르면 이를 최종 해결책으로 채택합니다.
1장에서 알고리즘의 시간 복잡도를 분석하는 도구인 빅오 표기법을 배웠습니다. 시간 복잡도 분석이라는 맥락에서 우리는 다음과 같은 두 가지 소요 시간을 측정합니다.
• 알고리즘이 후보 해결책(증명서)을 생성하는 데 걸리는 시간 tr
• 후보 해결책을 검증하는 데 걸리는 시간 ts