P - NP 간단히

알고리즘 수행시간 별 분류

• 상수 시간 알고리즘
  $O(1)$
  

• 선형 이하 시간 알고리즘
  $O(logN)$

• 선형 시간 알고리즘
  $O(N)$

• 다항 시간 알고리즘
  $O(N),O(NlogN),O(N^{100}), O(N^2 + M), ...$

• 지수 시간 알고리즘
  $O(2^N), O(N + 5^M), ...$

계산 복잡도 이론에서는 문제의 특성을 이렇게 정의한다

• P 문제
  다항시간 안에 답을 구할 수 있는 문제
  
  
  
• NP 문제
  구한 답이 정답인지 다항시간 안에 판별할 수 있는 문제
  
  
  
• NP-난해(NP-Hard) 문제
  다항시간 안에 답을 구하는 알고리즘이 발견되지 않은 문제
  
  
  
• NP-완비(NP-Complete) 문제
  NP-난해이면서 NP인 문제
  
  
  

"NP-난해 문제를 다항시간 안에 해결하는 알고리즘은 인류 역사상 아무도 생각해내지 못했다"

참고 : 구종만, 『프로그래밍 대회에서 배우는 알고리즘 문제해결 전략』 (서울:인사이트, 2012), 91-126