P & NP

알고리즘 9 P & NP

효율적인알고리즘이란

-다차시간알고리즘

다차시간알고리즘 : 최악의 경우 시간복잡도의 상한이 입력크기의 다항식인 알고리즘.

O(p(n)) 일 때, p(n) 이 다항식일 때.

2n, 3n^3+4n…..

2^n, n! 은 다항식이 아니다. = 다차시간알고리즘이 아니다.

다루기힘든문제 : 문제에 대해 다차시간 알고리즘을만드는 것이 불가능한 문제.

다루기힘든정도에따른분류

분류1. 다차시간알고리즘이 발견된 문제

분류1의 문제는 P집합.

-합병정렬,퀵정렬,이진검색,쉬트라센(행렬곱)

-연쇄행렬곱셈,최단경로구하기(플로이드),

-다익스트라,프림,크루스컬

분류2. 다루기 힘들다고 증명된 문제

분류2는 P, NP 어디에도 속하지 않음.

-비다항식 크기의 결과를 요구하는 비현실적문제

    = 모든 해밀토니안 회로 구하는 문제

-요구가현실적이지만,다차시간에풀수없다증명된문제

    = 종료문제,프레스버거산술문제

분류3. 다차시간알고리즘도 발견하지 못하고 다루기 힘들다고도 증명되지 않은 문제.

대부분의 문제가 여기 속함.

-0-1배낭채우기

-외판원(TSP)

-부분집합의 합 구하기

-m그래프칠하기

-해밀토니안회로구하기문제

최적화문제 vs 결정문제

최적화문제 : 가장 최적의 방법

결정문제 : 어떤 기준을 주어주고 기준을 만족하면 예 , 아니오로 대답. 기준값 주어줄 파라미터 필요.

최적화문제애 대한 다차시간 알고리즘이 있다면, 결정문제에 대한 다차시간 알고리즘도 쉽게 만들 수 있음.

집합P : 다차시간알고리즘으로 풀수 있는 모든 결정문제들의 집합.

TSP가 P에 속할까? 다차시간 알고리즘이 없다. 하지만, 다차시간으로 풀수 없다고도 증명을 못했다. 단정지을 수 없다.

-비결정적알고리즘 : 추측과 검증 단계로 이뤄져있고, 검증단계에서 사용하고 문제를 풀기위한 것은아님. 해답이 "존재-예", "존재-아니오" 가 나오면 푼다 라고 한다.

집합NP : 다차시간비결정적알고리즘으로하결할 수 있는 모든결정문제의 집합 = 문제가 NP에 속하기 위해선 반드시 다차시간에 검증을 할 수 있는 알고리즘이 존재하여야 한다.

-> 하지만, 문제자체를 해결할 수 있는 다차시간 알고리즘이 존재해야함을 의미하지는 않는다.

예) 외판원 문제는 (n-1)!개의 일주여행경로가 존재한다. 따라서, 다차시간에 그 문제를 해결할 수는 없다.  그러므로 NP.

P에 속하는 문제는 당연히 NP에도 속함.

NP에 속하지 않는 문제 = 다루기힘든문제(분류2)