[알고리즘] NP-Hard (Time Complexity)

Deterministic Algorithm VS Non-Deterministic Algorithm

1) Deterministic Algorithm
- input에 따라 결과가 정해진 알고리즘
- ex) A-> B로 결정되어 있는 알고리즘
2) Non - deterministic Algorithm
- input에 따른 답이 유일하지 않음. 대표적으로 Probablistic Algorithm이 있음.
- ex) A -> B,C,D 정해지지 않음.

P(Polynomial)

• 기본적으로 polynomial은 다항식의 라는 뜻 -> polynomial time 안에 해결이 가능하다는 이야기
• Deterministic Algorithm을 이용해서 다항 시간 내에 답을 구할 수 있는 문제의 집합
• yes/no로 답변이 가능

NP(Nondeterministic Polynomial)

• P(polynomial) 개념을 포괄하는 개념

• Non - Deterministic Algorithm을 이용해서 다항 시간 내에 답을 구할 수 있는 문제의 집합

• 답이 정말 yes가 맞는지 polynomial time 안에 확인할 수 있는 문제

• 다시 말해, 불확실한 상황에서 solution을 찾았다는 가정하에 polynomial time 안에 해결 가능함.

• NP-hard와 NP-Complete로 나뉨

NP-hard

• 다항 시간 내에 풀 수 없는 문제
• 시간복잡도를 Deterministic Polynomial으로 구성할 수 없음
• 다시말해 모든 수를 일일이 확인해 보아야 함

linear classification, K - means Clustering등의 시간복잡도를 확인하여 보자.