[알고리즘] 기본 개념 정리 (12) - P-NP 문제와 알고리즘의 내일

다항시간 알고리즘의 뜻

• 최악의 경우 시간복잡도의 상한을 다항함수의 꼴로 표현할 수 있는 모든 종류의 알고리즘
• 해를 얻었다는 것은 그 해에 대한 검증이 이미 끝났다는 것을 의미
  • 모든 P-문제는 자명히 NP-문제
    • P-문제(Polynomial) - 문제에 대한 해를 도출하는 다항시간 알고리즘이 하나 이상 존재하는 경우
    • NP-문제(Non-deterministic Polynomial) - 문제에 대한 해를 검증하는 다항시간 알고리즘이 하나 이상 존재하는 경우
    • NP-문제가 P-문제를 포함함

P-NP 문제의 이해

• P-문제와 NP-문제의 포함관계?
  • 정의로부터 NP가 상위인 것은 분명, 가능한 경우는 서로 같은 것이거나 같지 않은 경우
• NP-난해 문제
  • 다음의 조건을 만족하는 X
    • NP 클래스에 속하는 모든 문제를 다항시간 내에 X 문제로 환원시킬 수 있음
• NP-완전 문제
  • (P ≠ NP인 경우) NP 문제이면서 NP-난해 문제인 모든 문제

• P = NP인 경우