NP-complete

NP-hard

- Non-deterministic Polynomial-time hard

- 결정 문제의 분류로 모든 경우의 수를 확인해보는것 이외에는 답을 찾을수 업슨ㄴ 문제

 

NP-complete

- NP 중에서 가장 어려운 문제

 

 

NP-complete 해결을 위한 접근 방법

- 근사 approximation : 적절한 범위 내 차선의 suboptimal 해결책을 빠르게 찾는 알고리즘. 모든 np-complete 문제가 좋은 근사 알고리즘을 가진것이 아니며, 발견하더라도 문제 자체를 해결하기엔 충분치 않음

- 확률 probabilistic : 문제의 인스턴스에 대한 확률분포에 대해 좋은 평균 런타임 동작을 낳는다고 입증된 알고리즘

- 휴리스틱 : 많은 경우 잘 동작하지만, 항상 빠르다는 증명은 없는 알고리즘

- 스페셜 케이스 : 문제의 인스턴스가 특별한 경우라면 빠르다는 것이 입증된 알고리즘

 

 

 

새로운 문제의 NP-complete 증명 방법

- 이미 알려진 NP-complete 문제를 새로운 문제로 환원 reduce

 

 

NP-complete 문제 종류

- Boolean statisfiability problem SAT

- Fifteen puzzle

- 배낭 문제

- minesweeper

- tetris

- 해밀턴 사이클 문제

- 순회 판매원 문제

- subgraph isomorphism problem