P/NP & Approximation Algorithm

1. 해결 가능한 문제/해결 불가능한 문제

P-완비 문제들은 현실적인 시간내에 풀 수 없는 문제들 (지수시간)이다.
다항식 시간, 현실적인 시간 -> 입력의 크기 n의 다항식으로 표시되는 시간
비다항식 시간, 비현실적인 시간 -> 지수시간, 계승시간 등

2. 결정적 문제 / 최적화 문제

결정적 문제: Yes/No 문제, 존재의 여부 파악
최적화 문제: 문제의 최적값을 찾는 문제

3. NP 완전문제

결정적 문제에만 국한되는 문제이지만, 최적화 문제와 밀접환 관계를 가진다.
결정문제가 풀린다면 최적화 문제도 풀리고
결정문제가 안풀린다면 최적화 문제도 안풀린다.

4. P/NP

P: 다항식 시간 내에 결정 문제 해결 가능
NP: P를 포함, 아직 P라고 해결되지 않은 문제, 해를 제공, 해당 해가 Yes임을 다항 시간 내에 확인 가능하다면 NP 문제이다.

5. 다항식 시간 변환

문제 A의 입력 예시 x로 부터, 문제 B의 입력 예시 y를 항상 만들 수 있다면,
그러한 함수 Tfmf transformation이라고 한다.
변환 함수 T를 다항 시간에 수행할 수 있다면 문제 A를 문제 B로 다항 시간 문제 변환이 가능하다고 하며
A ∝ B라고 표현한다.