4장 알고리즘 분석

4.7 계산 복잡도 클래스: P, NP, NP-완비

Decision Problem vs. Optimization Problem

Decision Problem

Yes-no question on an infinite set of inputs.

주어진 정수는 소수인가?

Optimization Problem

Finding from the best solution from all feasible solutions

주어진 예산제약 내에서 효용을 극대화하는 소비집합은 무엇인가?

P/NP Problem

Complexity Class

같은 성질의 복잡도(related resource-based complexity)를 가진 문제들의 집합

여러 기준으로 문제들을 분류할 수 있지만 polynomial time을 기준으로 나누면 P문제와 NP문제로 나눌 수 있다.

Polynomial Time(다항식 시간)

실행 시간의 upper bound가 다항식인 알고리즘

T(n) = O(n^k), k >= 0

eg) O(logn), O(n), O(nlogn), O(n²), O(n³), …

= tractable

P-Problem (P문제)

A problem is assigned to the P (polynomial time) class if there exists at least one algorithm to solve that problem

Polynomial time algorithm이 존재하는 문제들의 집합

NP-Problem (NP문제)

Set of decision problems for which the problem instances have proofs verifiable in polynomial time

답이 주어졌을 때 이것이 정답인지를 polnomial time 내에 확인할 수 있는 문제

P문제들의 집합을 P-Class, NP문제들의 집합을 NP-Class라고 한다.

Reduction(환산)

한 문제를 다른 문제로 바꿔서 푸는 기법

문제 B의 입력을 적절히 변형해 문제 A의 입력으로 바꾸는 환산 알고리즘이 존재한다면 B는 적어도 A를 푸는 가장 빠른 알고리즘으로 풀 수 있다.

그래서 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠르다.

즉, A가 B 이상으로 어렵다.

NP-Hard / NP-Completeness

NP-Hard Problem

at least as hard as the hardest problems in NP

적어도 모든 NP문제만큼은 어려운 문제들의 집합

NP에 속하는 모든 decision problem을 polynomial time에 환산(reduce)할 수 있는 문제들의 집합

NP-Completeness Problem

NP-Hard문제 중 NP문제들의 집합

Back to top ↑