[계산이론](27)[P & NP]

class P

SDTM이 다항시간(polynominal time) 안에 문제를 풀 수 있음
    $P = \bigcup_{k}TIME(n^k)$
    즉, 시간 복잡도가 O(n), O(n^2), O(n^30), ....
    이떄 practicaly solvable하다 한다

 

PATH problem

s -> t인 경로가 존재하는가?
PATH는 다항시간 내에 풀 수 있는 알고리즘이 있다.
    $PATH \in P$

 

노드가 v개 있을 때, 단순하게 브루트 포스로 풀면...
    O($v^v$)의 시간복잡도를 갖게 된다.

 

그러나, BFS로 풀면...
    1. s에 .을 찍는다
    2. s와 연결된 노드 중 .이 안찍혀 있는 노드는 .을 찍는다
    3. 만약 t가 .이 찍혔다면 accept
    O(V+E) <= O(n+n^2) = O(n^2)
-> 따라서 PATH의 poly time algorithm이 존재하므로 PATH ∈ P

 

CFL ⊆ P

CFL은 대응하는 CFG가 있음 -> chomsky normal form으로 나타낼 수 있음
-> 최대 2n-1번의 연산만 해보면 됨

 

멍청하게는 이런 2n-1번의 계산을 분기별로 전부 해보면 된다
O($b^{2n-1}$)의 시간복잡도

 

그러나 dynamic programming을 이용하면... (CYK algorithm)
    1. chomsky normal form을 이용해 생성할 문자열을 쪼갠다
    2. 가장 단순한 문자부터 올라가며 원본 문자열을 생성한다
        길이 N자리를 만들게
                근데 이 문자열을 한칸씩 옆으로 가며 만들어보자
                    이걸 어떻게 분할해서 만들까?
    -> 총 O(n^3)의 시간 복잡도

 

class NP

"아직" poly해결책이 나오지 않은 문제
⇔ NTM으로 다항시간 내에 풀 수 있는 문제
    NP = $\bigcup_k NTIME(n^k)$

⇔ polynomial verifier가 존재하는 언어

 

verfier

답 후보를 주면 답인지 아닌지 판정하는 알고리즘
    hamPATH가 있는가? -> 이게 hamPATH인가?
    A = {w | V accepts <w, c>}
        c는 증거

• polynominal verifier
  다항시간 안에 후보가 답인지 아닌지 판정
  -> 물론 없는 경우도 있다. (이때는 co-NP에 포함)
  
  

증명

• poly NTM -> poly verifier
  증거 c를 매 NTM의 step마다 선택한 선택지의 순서를 기록
  이떄, NTM이 poly하므로, c도 poly 안에 있다
  c에 적힌 순서대로 V(w, c)도 정확히 따라감
  이떄 O(n^k)의 시간이 걸림
• poly verifier -> poly NTM
  V와 c가 존재할 때,
  NTM은 가능한 모든 경우에 대해 c를 적고
  이걸 다시 V에 돌리고 accept, reject 판정
  
  

Hamiltonian path

모든 노드를 중복 없이 1번씩 방문하는 방법이 있는가?

현재 알려진 방법으로는 브루트포스나 dynamic programming이 있으나,
    최대 O($n^22^n$)의 시간복잡도... (exp)