210713 NP vs P

Polynomial problems(P) : 다형식 시간으로 해결되는 문제 ex) 정렬 : O(nlog n) , O(n^2) , 등등

Exponential problems(E) : 지수 부분이 n에 따라 무한대로 증가하는 문제 ex) n^n , n^(n^2), 2^n

Interactable (Non - Computable) Problems (I) -> 결정할 수 없는 문제 ex) Halting (어떤 프로 그램이 무한 루프에 빠지는지 알아내는 알고리즘)

 

알고리즘에서 핵심적인 문제 :

Exponential 문제를 푸는 법은 아는데 이것을 polynomial time에서 해결하는 방법, 애초에 할 수 있는지를 모름

Ex) 0/1 Knapsack -> O(nW) -> O(2^n) 되면 Exponential  이것을 polynomial 로 해결할 수 있는지 모름

 

Deterministic 알고리즘 - 모든 수행의 결과가 유니크하게 결정됨 (현재의 알고리즘)

Non-deterministic 알고리즘 - 이론상의 알고리즘, 현재의 컴퓨터로는 X, 여러 결과들 나옴=> 그들 중 하나 고른다

• 기본 Operations
  • Choice(S) - 결과들 중 하나를 선택 , 상수 시간 사용하여 올바른 결과 선택 (이상적)
  • Verification -
    • 성공
    • 실패
• 기본 동작
  1. Choice()를 사용하여 문제의 답을 찾는다  (guessing stage)
  2. 앞서 찾은 답이 올바른 답인지 check, polynomial 시간 사용

 

예시

 

NP(Non-deterministic Polynomial) :  Non-deterministic 알고리즘으로 Polynomial 하게 해결할 수 있는 문제

P : deterministic Polynomial

P는 NP의 부분집합

 

충족가능성 문제( Satisfiability Problem , SAT) :

어떠한 변수들로 이루어진 논리식(boolean expression)이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이다

 

CNF (Conjunctive Normal Form==논리곱으로 이루어진 논리식) Satisfiability

DNF (Disjunctive Normal Form==논리합으로 이루어진 논리식) Satisfiability

 

Cook's 이론

SAT 문제가 P면 모든 P는 NP로 해결가능

 

Decision Problem : 다른 말론 Yes, No Problem. 결과가 Yes 아니면 No로 나오는 문제

Ex) 해밀토니안 사이클 문제

 

NP 난해 (NP - Hard) : NP 클래스 안에 모든 문제 (B)가 어떤 문제 (A)로 reduction(환원) 할 수 있으면 A는 NP 난해 문제이다

*reduction : 문제 A를 쉽게 풀 수 있을 때, 문제 B 도 풀 수 있는 것이 당연하다면 B를 문제 A로 환원시킬 수 있다(reducible) 라고 표현한다. 즉 문제 A의 난이도가 문제 B보다 어렵다는 것을 알 수 있다.

 

NP 완전 (NP - Complete) : NP - Hard 이면서 NP 인 문제 (가장 어렵다) 

즉, NP-Complete 중 하나라도 Polynomial 시간 내에 해결한다면, reduction 을 통해 모든 NP들을 Polynomial 시간에 해결할 수 있다. 그러한 경우가 위의 그림의 P=NP의 경우 

반면 반대로 하나도 Polynomial 시간내에 해결하지 못한다면, P != NP 의 경우가 될 것이다.

 

 

*쉬워보이는듯 했으나 제대로 이해못함... 어렵다!!