[암호학] 16. Complexity Classes

지난시간 Problem의 시간을 제한하자는 아이디어가 나왔다.

하지만 시간을 몇초, 몇분 이렇게 제한할 수 없으니 일반적으로 제한한 개념이 있다. (big-O표기법과 비슷하다.)

 

Time-Limited Complexity Classes

$P$ : DTM이 다항시간에 해결하는 Problem 집합 

$NP$ : NTM이 다항시간에 해결하는 Problem 집합

$EXP$ : DTM이 지수시간에 해결하는 Problem 집합

$NEXP$ : NTM이 지수시간에 해결하는 Problem 집합

$DEXP$ : DTM이 지수의 지수시간에 해결하는 Problem 집합 ($2^{2^n}$)

...

(뒤에 $P$-class처럼 class가 붙어야하지만 생략합니다.)

예를들어 보면 우리가 사용하는 컴퓨터인 DTM은 정렬문제를 $O(n)$~$O(n\log{n})$에 해결할 수 있다.

이는 다항식 범위에 속하므로 $P$이다.

소인수분해나 소수판정은 $NP$에 속한다고 한다. (소수판정은 확실하지 않음)

저는 소수판정을 $O(\sqrt{n})$에 할 수 있는데요? 이거 $P$아닌가요?

소수판정문제는 어떤 수 $n$이 주어지면 해당 비트수를 기준으로 시간을 측정한다.

즉 $O(\log{n}^c)$모양이 나와야 $P$이지만 루트가 나왔으므로 적어도 $NP$이상이다.

 

Space-Limited Complexity Classes

$P$-$SPACE$ : DTM이 다항공간을 사용하여 해결하는 Problem 집합

$NP$-$SPACE$ : NTM이 다항공간을 사용하여 해결하는 Problem 집합

...

이제는 공간을 제한한다.

우리는 시간제한이 더 중요하니 크게 볼 일은 없을 것 같다.

 

Lemma. $P$-$SPACE \subseteq EXP$

만약 공간을 $O(n^c)$개 쓴다고 하자.

여기에 $O(c^n)$개의 상태를 넣으면 비둘기집의 원리에 의해 중복되는 경우가 나온다.

따라서 포함관계가 성립한다.

 

Time-Space 관계

$P \subseteq NP \subseteq P$-$SPACE = NP$-$SPACE \subseteq EXP $...

위와 같은 포함관계가 성립한다고 한다.

우선 $P \neq EXP$라는건 알려져 있다. (증명은 굉장히 어렵다.)

그렇다는건 위의 $\subseteq$들중 적어도 하나는 $\subset$이 되어야 한다. (전부 다 일수도 있다!)

그중에서는 난제로 유명한 $P=NP$도 있다.

만약 $P \subset NP$라면 $P \neq NP $라는 것이고 세계는 대 혼란을 겪게 된다.

하지만 현재까지 위의 3개 중 어디에 등호가 빠지는지 모른다고 한다...

 

$P$-$SPACE = NP$-$SPACE$는 Savitch Theorem에 의해 참이라고 한다. 관심있으면 찾아보자.

 

$NP$-Complete

$NP$-Complete는 $NP$에 존재하는 Problem중 어려운 것들의 집합이다. (어려운건 오래걸리는 것)

Longest-Path, SAT, salesperson문제등이 알려져있다.

 

여담으로 싱글플레이 게임을 $NP$-Complete로 만들면 사람들에게 인기가 있다고 한다.

만약 $NP$-Complete보다 쉬우면 사람은 지루함을 느끼고 그보다 어려우면 너무 어려워서 흥미를 잃는다고 한다.

$NP$-Complete게임으로 잘 알려져 있는것은 슈퍼마리오, 소코반, 지뢰찾기등이 있다. (실제로 재미있다.)

또한 멀티플레이는 $P$-$SPACE$ Complete이면 재미를 느낀다고 한다. 

 

$NP$-Hard

$NP$-Hard는 $NP$-Complete보다 어렵고 심하면 $NP$밖에 있을 수 있다. (문제의 하한이 $NP$라는 것이다.)

$NP$-Complete = $NP \cap NP$-Hard로 볼 수 있다.

 

 

---

앞에서 배경지식을 알고 오니 용어와 의미에 대한 이해가 빠르게 되는 것을 알 수 있다.