P-NP 문제

Polynomial  vs Non-deterministic Polynomial

참고 –
https://namu.wiki/w/P-NP%20%EB%AC%B8%EC%A0%9C
https://en.wikipedia.org/wiki/Maximum_common_induced_subgraph

두 개의 그래프에서 공통된 최대 부분 그래프를 찾고자 한다.
요 문제가 NP-complete문제라고 한다.

내가 이해한 NP문제란.. 직관적으로는 알겠는데 수학적으로 이게 다항식 내로 풀리는 문제인가? 라고 증명하기에는 어려운… 뭐 그런문제를 말한다고 한다.

두개의 그래프에서 공통된거가 있다는 것도 알고 있지만 어떻게 구할 것인가에 대해서는 음… 애매해.. 라는 느낌?

다른 사람 예…

NP 문제는 결정 문제들 중에서 적어도 검산은 쉽게 할 수 있는 것을 모아 놓은 집합으로도 정의할 수 있다. 정확히 말하면, 어떤 결정 문제의 답이 YES일 때, 그 문제의 답이 YES라는 것을 입증하는 힌트가 주어지면, 그 힌트를 사용해서 그 문제의 답이 정말로 YES라는 것을 다항식 시간 이내에 확인할 수 있는 문제가 바로 NP 문제에 해당된다. 예를 들어, \{-5,6,1,2,-10,-7,13\}{5,6,1,2,10,7,13}과 같이 정수 nn개로 이루어진 집합이 주어졌다고 할 때, ‘이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?’라는 문제는 아직까지 다항식 시간 알고리즘이 알려져 있지 않다. 곰곰히 생각해보아도, 그냥 모든 부분집합을 다 테스트해보지 않는 이상 답이 YES인지 NO인지 답하기가 어렵다는 것을 알 수 있다. 그렇지만 누군가가 우리에게 \{6,1,-7\}{6,1,7}이라는 힌트를 제공하였다면, 우리는 먼저 이 집합이 원래 집합의 부분집합이라는 사실을 확인하고, 이 집합의 원소의 합이 0이라는 사실을 확인함으로서, 원래 문제의 답이 YES라는 것을 어렵지 않게 확인할 수 있다. 따라서 ‘크기가 nn인 어떤 정수 집합이 주어졌을 때, 이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?’라는 문제는 적어도 NP 문제인 것은 확실하지만, 이것이 P 문제인지 아닌지는 아직 모르는 상황이라고 할 수 있다.

NP문제를 쉽게 설명하자면 yes/no로 답할 수 있는 문제중에,
yes라는 답에 해당하는 구체적인 예를 줬을때, 그것이 yes가 맞다는것을 빠른(polynomial)시간안에 알 수 있으면 NP문제이다.

출처: http://yoonho.info/19 [꿈꾸는 프로그래머]

NP-complete 라고 하면…
NP-complete 문제를 풀 수 있으면 모든 NP문제를 풀 수 있게 된다… 라는 뜻으로
NP 문제들 중에 가장 어려운 종류의 문제라고 한다.

NP문제가 뭔지 궁금했다.