| NP 완전 문제 | 여러 가지 NP 완전문제 | NP-완전성과 변환성 |

NP 완전 문제

■ 문제의 일반적인 분류

① 다항식 시간 알고리즘을 찾은 문제

- 모든 알고리즘들이 다항식 시간 알고리즘인 경우
            정렬 문제 : (nlogn). 행렬곱셈 문제 : (n^2.38)

- 지수적인 알고리즘도 있으나, 다항식 시간 알고리즘을 찾은 경우
            연쇄행렬곱셈 문제, 최단경로 문제, 최소비용신장트리 문제

② 다루기 힘들다고 증명된 문제

- 비다항식(nonpolynomial) 크기의 결과를 요구하는 비현실적인 문제
          보기 : 모든 해밀토니안 회로를  결정하는 문제
                    만일 모든 정점들 간에 이음선이 있다면, (n-1)! 개의 답을 얻어야 한다.
                    이러한 문제는 하나의 해밀토니안 회로를 구하는 문제에 비해서 필요이상으로                     많은 답을 요구하므로 사실상 비현실적이고, 다루기 힘든 문제로 분류된다.

- 요구가 현실적이나, 다항식 시간에 풀 수 없다고 증명된 문제
          놀랍게도 이런 부류에 속하는 문제는 상대적으로 별로 없다.
          예를 들면, 종료 문제(Halting Problem)와 같은 결정 불가능한 문제(Undecidable           Problem) - 그 문제를 풀 수 있는 알고리즘이 존재할 수 없다고 증명이 된 문제

③ 다루기 힘들다고 증명되지 않았고, 다항식 시간 알고리즘도 찾지 못한 문제, NP문제가 이러한     문제이다.

• 0-1 배낭 채우기 문제, 외판원 문제
• m-색칠하기 문제(m3), 해밀토니안 회로 문제