9장 Theory of NP

• 공부할 때 참고한 블로그 : https://sepang2.tistory.com/

학습기록

Ch:9: Theory of NP

• 다항시간 알고리즘이란 worst case 시간복잡도가 n에 대한 다항 함수로 구성되는 알고리즘이다. o(n^k) (K≥0)
• 다만 n^3을 넘어가는 다항시간 알고리즘 또한 실제 사용하기에는 복잡도가 커다는 평가가 있다.

solvable problem

• 컴퓨터가 해결할 수 있는 해결할 수 있는 알고리즘이 입증되어 있는 경우를 말한다. polynomial of expoenential시간 복잡도를 가진다.

unsolvable problem

• 미래에도 해당 문제에 대한 해결 알고리즘을 개발하는게 불가능하다는 것이 증명된 문제들을 말한다.

intractable problems

• 다루기 어려운 문제=해당 문제 유형의 모든 알고리즘(과거,미래 포함) 다항시간보다 시간 복잡도가 더 크다는 것이 증명된 문제들 = P도 NP도 아닌 문제임.

tractable problems

• 다루기쉬운 문제 = 해당 문제 유형에 기존 알고리즘 중 적어도 하나는 다항시간 알고리즘을 가지며 class P에 속하는 문제.

둘다아닌경우

• 아직 증거가 없고 NP class에 속하는 문제 =0-1 kanpsack문제 =현재까지 다항시간 알고리즘이 발견되지 않았으며 미래에 다항시간 알고리즘을 개발하는 것이 불가능하다고 증명도 못한경우.
• intractability(난해성) = 문제 고유의 속성. = 비다항 시간 알고리즘이 발견되었다고 난해한문제라고 말할 수 없다.
• 계산 복잡도 이론의 주요 목적은 문제의 고유한 난이도에 따라 문제를 분류하는 것임.
• 일부 문제들은 비다항 개수만큼의 출력을 필요로 하기에 다루기 힘든 문제도 있다. 출력이 n!정도면 빡세겠지

NP 이론

Deterministic algorithm

• yes or no 형식의 답을 요구하는 문제.

Optimization algorithm

• 답의 경우의 수가 무한하고, 가장 좋은 해를 요구하는문제
• NP이론이란 tractable하지도 intractable하지도 않은 문제 사이의 관계를 발전시키는데 중점을 두는 이론이다.
• deterministic 문제만으로 연구를 제한해야 NP이론의 발전이 쉽기때문에 결정 문제만을 사용한다.
• 각 최적화 문제에는 해당하는 결정 문제들이 있다. 이 최적화문제에 해당하는 결정 문제에 대한 다항시간 알고리즘을 개발한다면 해당 최적화 문제에 대한 다항 시간 알고리즘도 미래에는 얻을 수 있음이 입증되어있다.
• 최적화 문제에 해당하는 결정 문제란 kanpsack문제가 주어지고, w와 p가 주어져서 총무게 ≤ W 이면서, 총이익 ≥P인 것중에서 최적값을 찾는 문제와 같은 경우를 이야기한다.

Non deterministic algorithm

ex) 외판원 문제에 결정문제를 설정

• 고향에서 시작하여 모든 도시를 한번씩 방문하고 고향 도시에서 끝나는 최단 경로가 맞냐틀리냐? - (결정문제 추가) 단 weight가 15여야한다.
• 그러면 컴퓨터는 무작위로 tour 목록을 생성한다. (추측 단계 tour는 최단 경로가 아닌 그냥 고향에서 시작하여 모든 도시를 한번씩 방문하고 고향 도시에서 끝나는 경로들의 집합임) tour가 맞는지 1차검증하고 weight가 15인지 2차검증을 하여 (검증단계) True False를 출력한다. 여기서 검증 알고리즘이 다항 시간 알고리즘이라면 해당 알고리즘은 다항 시간 비결정론적 알고리즘 이라고 한다.
• 문제를 해결함에 있어 검증 알고리즘이(2) 다항시간 알고리즘이라면 해당 알고리즘은 다항 시간 비결정적 알고리즘 이라고 한다.
• 비결정론적 알고리즘이란 어떤 힌트를 검증하는 결정론적 알고리즘으로 대체 가능하다.

P , NP class의 정의

P class

• 결정론적 다항시간 알고리즘으로 해결할 수 있는 모든 결정 문제의 집합. = 어떤 결정 문제 X에 대해 주어지는 입력이 참인지 거짓인지를 다항 시간 안에 결정론적으로 해결하는 알고리즘이 존재하는 문제 = kapsack 문제에서 무게 w 이하 이익 p 이상이 되도록 배낭에 담는게 가능하냐 아니냐에 대한 대답이 다항시간안에 답을 내릴수 있는 경우도 포함.

NP class

• 다항 시간 비결정적 알고리즘으로 해결할 수 있는 모든 결정 문제의 집합 = 어떤 결정 문제 x에 대해 주어지는 입력이 참인지 거짓인지를 다항시간에 비결정론적으로 해결하는 알고리즘이 존재하는 문제
• 다항시간 안에 결정론적으로 검증 가능한 문제들의 집합=어떤 결정 문제 X에 대해 어떤 입력과 어떤 크기의 어떤 다항식으로 표현되는 크기를 갖는 증거를 함께 제공받았을 때 이를 다항시간에 결정론적으로 검증하는 알고리즘이 존재하는 문제=무수히 많은 해중에서 주어진(결정된) 상황에 대해서만 검증했을 때 검증하는 알고리즘이 다항시간인 문제. 바로 위의 외판원 문제가 예시임.
• 즉, 힌트가 주어지고 힌트를 사용해 결정문제의 답을 다항시간안에 밝혀낼 수 있으면 NP class이다.
• 답을 알고있어, 그거 따라가기만 하면되는데 그 시간이 polynomial이냐

• 위 그림은 모든 결정문제의 집합을 보여주며 NP가 P와 동일할 수 있음을 의미하는데 아직 증명은 이루어지지 않았다.

NP complete 의 기본개념

• CNF satifiability problem = 충족 가능성 문제 = NP complete problem = 4가지 부울 표현식을 다룸

• CNF - 충족 가능성 결정 문제는 CNF에서 주어진 논리적 표현의 논리적 변수에 참과 거짓 값을 할당하여 전체 표현을 참으로 만드는 것이 가능한가?
• instance 1 은 yes x1=true , x2=true x3=false라면 가능함.
• instance 2는 no 불가능.
• CNF문제는 확실히 NP 문제에 들어가는데, 아무도 이 문제의 다항시간 알고리즘을 찾지 못했고, 미래에 다항시간에 풀 수 없다는 것을 증명하지 못했기 때문임.(그래서 Pclass 인지는 알 수 없음.) 또한 instance가 주어지고, true false 값에 대한 입력이 주어질 떄 이런 특정 할당(결정론적인)의 경우 다항시간 알고리즘을 작성하는 것은 가능하기에 NP 문제임

Trasnformation algorithm

• 목표 = 가장 어려운 NP 문제를 찾는것. = 다항시간 으로 NP 문제를 가장 어려운 NP 문제로 변환가능하고, 그렇게 얻은 가장 어려운 NP 문제로 P = NP 또는 P ≠NP를 증명한다면 위에서 해결하지 못한 답을 내릴 수 있을 것이다.

• NP hard = NP class의 다른 문제를 다항시간 안에 변환 가능한 문제
• 문제 B는 NP class에 속하면서, 모든 NP 문제를 다항 시간안에 B로 변환 가능하면 B는 NP-complete문제라고 한다.

• P,NP,NP-complete간에 생길 수 있는 관계 3가지

1. P가 NP의 부분집합인경우 = 아직까지 NP이면서 P가 아닌 문제들이 알려지지 않았음.
2. P=NP이면서 NP-complete와는 같지 않은 경우
3. P≠NP인 경우

그래서 모든 NP문제를 다항시간안에 변환 가능한 NP -complete 문제가 있고, 이 NP-complete문제를 다항시간 안에 풀어버린다면 모든 NP 문제는 P문제와 같아질 것이다. NP = P가 성립된다. 풀 수 없다는것을 증명해도 NP≠P에 대한 증명이 될것이다.