P와 NP

• 복잡도가 logN, N, NlogN, N^2와 같이 다항식으로 표현되는 부류의 문제를 다항(Polynomial)을 의미하는 P라고 부른다.
• 2^N과 같이 다항으로 표현할 수 없는 문제들을 비결정적 다항을 의미하는 NP(Nondeterministic Polynomial)라고 부른다.
• NP 문제는 해결책을 빨리 찾을 수는 없지만, 어떤 해결책을 알고 있다면 그것이 맞는지는 빨리 입증할 수 있다.

여행하는 외판원 문제 (traveling salesman problem)

• 외판원은 자신이 사는 도시에서 출발해 어떤 순서로든 다른 도시를 모두 방문하고 나서 다시 출발점으로 돌아와야 한다.
• 여기서 목표는 각 도시를 정확히 한번씩(반복없이) 반문하고, 전체 여행한 거리를 최소로 만드는 것이다.
• 이러한 문제는 아직도 최단 경로를 찾는 방법은 모든 가능한 경로를 시도해 보는 것 밖에 없으며, 예전보다 좀 더 기발해졌을 뿐이다.
• 여행하는 외판원 문제의 10개 도시에 대해서 모든 경우의 수는 181440개이다.
• 이러한 문제들은 굳이 가장 이상적인 해답을 쓸 필요가 없을 때 현실적으로 정답에 가까운 해결책을 찾기 위해 설계된 기법인 휴리스틱 방법을 사용한다.

P-NP 문제

• 수학계의 최대 난제인 7개의 밀레니엄 문제 중 하나. (이 중 푸엥카레 정리는 증명됨)

• P 집합과 NP 집합이 같은지 다른지를 증명해야 하는 문제다. P 집합은 이미 NP의 부분집합이므로, 모든 NP 문제가 P 문제라는 것을 밝히면 P 집합과 NP 집합은 같은 것이 된다. 1971년에 처음 제시되어 50여 년이 지났음에도 아직 풀리지 않고 있다.

• 위 말을 일상적인 표현으로 바꾸면 "쉽게 검산할 수 있는 모든 문제들은 모두 쉽게 풀리는가?"이다. 만일 어느 한쪽으로 증명이 된다면 셋 중 하나의 결론을 도출하게 된다.

  • 같다: 쉽게 검산할 수 있는 풀기 어려운 공식은 풀기 쉬운 공식으로 변형될 수 있다.
  • 다르다: 풀기 쉬운 공식으로 변형될 수 없는 어려운 문제가 존재한다.
  • 증명할 수 없다.

• 이해한 대로 설명해보자면

• NP문제는 위의 외판원 문제의 예시처럼 모든 경우의 수를 다 따져보는 것 외에는 답을 찾을 수 없는 경우. 그리고 그 모든 경우의 수를 다 따져보는 방법의 복잡도가 다항식 이상의 복잡도를 같는 경우인 것같다.

• 만약 P와 NP가 같단 것으로 증명이 된다면, NP문제들도 다항복잡도로 푸는 방법이 존재하지만 우리가 아직 그 방법을 발견하지 못한게 된다는 것이고