나름 개발자의 IT블로그

지난시간 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은 정렬문제를 $..

자 이쯤되면 필요한 배경지식은 모두 쌓은것 같네요. 이제 암호학을 배우러 가보도록 하죠 첫 시간에 봤던 그림이다. M -> C로 암호화하는 Problem X1가 있을 것이고 C -> M으로 복호화하는 Problem X2가 있을 것이다. 즉 위 그림에서 1번에 X1이 들어가고, 2와 3번에 X2가 들어간다. 그럼 가장 베스트인 경우는 2는 해결할 수 없고 3은 해결할 수 있으면 좋을 것이다. (1은 언제나 해결 가능해야 함..) 그것이 가능할까? Solvable vs Unsolvable Solvable은 말 그대로 해결할 수 있는 Problem, Unsolvable은 해결할 수 없는 Problem이다. Class D에 포함되는 Problem들은 Solvable하다. (Yes, No가 출력으로 나오니까..)..

Dove-Tailing Technique Classes E 는 Enumerable 한 Problem들의 집합이라고 정의했다. 왜 그런지 알아보자. Classes E는 문제를 해결할 때 String 단위가 아니라 String안에 있는 Symbol단위로 진행한다. 예를들어 $S_1 = a_{11}a_{12}a_{13}..., ..., S_i = a_{i1}a_{i2}a_{i3}$이 있으면 $a_{11} \rightarrow a_{12} \rightarrow a_{21} \rightarrow a_{13} \rightarrow a_{22} \rightarrow a_{31} \rightarrow \dots$이런식으로 진행하며 해결한다. 이런 방법을 Dove-Tailing Technique이라고 하고 이 때문에 E..

Classes Complexity Theory에서 Classes란 Problem들의 집합을 의미한다. 우리는 앞에서 Problem이 무엇인지 알고 왔기 때문에 Classes도 큰 어려움없이 이해할 수 있다. Problem의 크기가 $|2^{|\Sigma^*|}|$였으므로 Classes의 크기는 $|2^{|2^{|\Sigma^*|}|}|$가 되고 이는 어마어마하게 많다는 것을 의미한다. 그리고 앞서 말했듯이 쉬운 문제 -> 빨리 풀린다, 어러운 문제 -> 푸는데 오래 걸린다, 굉장히 어려운 문제 -> 푸는데 언제 끝날지 모른다. 를 의미한다. 그럼 이제 Classes에는 어떤 것들이 있는지 알아보자. Classes D Classes D는 Decidable한 문제로 입력 $x$가 Language $L$에 포..

Turing Machine 이제 우리의 컴퓨터와 가장 가까운 튜링 머신이다. 튜링 머신이 가장 강력한 머신임은 모르지만 모든 문제를 풀 수 있는 General Machine이라고 한다. 다른 말로 튜링 머신으로 풀 수 없는 문제는 어떤 머신을 가지고 와도 해결할 수 없다. 우선 튜링머신의 구조는 아래와 같다. 가장 위쪽부터 작은 네모들의 집합이 Tape이다. Tape에 symbol을 남길 수 있다. 그리고 Tape에 들어있는 각 네모 칸이 Cell이고 이 곳 하나당 symbol하나를 기록할 수 있다. 현재 Cell위치를 가리키는 화살표가 R/W head이다. head를 이용하여 현재 Cell에 적힌 symbol을 읽거나 새로 쓸 수 있다. 밑에 있는 P, Q, R, S는 각각 state를 의미하고 현재 ..

암호학을 위한 Computation Theory가 끝나가고 있다. 지금은 배경지식을 알아가는 단계이니 가벼운 마음으로 알아가보자. Some Problems 여러가지 문제를 보자. $L8 = \{x|x=y2y^R2y^R, y \in \{0, 1\}^*\}$ $L9 = \{x|x=y2y^R2y^R2y^R, y \in \{0, 1\}^*\}$ $L10 = \{x|x=yy^Ry^R, y \in \{0, 1\}^*\}$ $L11 = \{x|x=yy^Ry^Ry^R, y \in \{0, 1\}^*\}$ $L12 = \{x|x=yy, y \in \{0,1\}^*\}$ 위 문제들은 DPDA로 해결할 수 없다. 특히 $L12$는 NPDA로도 해결할 수 없다. (ㄷㄷ..) 하지만 stack을 2개 사용하여 해결할 수 있다...

계속해서 배경지식에 대한 설명이 나오고 있다. 지금 내용들을 알아야 뒤에 나오는 개념들이 이해되니 천천히 알아보도록 하자.. Problem X5를 AC하는 머신이 있는가? 우리는 Problem X5가 DFA로 AC를 받을 수 없다는 것을 Pumping Lemma로 보였다 NFA로도 나타내기 힘들어 보이는데 여기에 stack를 하나 추가하는 것 만으로도 해결할 수 있다. DFA에 stack을 추가한 머신을 Deterministic Push Down Automata라고 한다. 여담으로 머신 $\in$ 튜링머신(컴퓨터)이다. Deterministic Push Down Automata (DPDA) 위에서 설명했듯이 DFA에 stack을 추가한 머신이다. 상태를 stack으로 관리하고 입력에 따라 스택에 넣을지 ..

NFA (Non-Deterministic Finite Automata) 이번엔 "비결정적 유한 오토마타"이다. 역시 상태는 유한하지만 입력이 들어오면 이동할 상태가 비결정적이라는 뜻이다. NFA는 다음으로 이루어져있다. $M = (Q, \Sigma, q, F, s)$ $Q$ : NFA상태들의 집합 $\Sigma$ : 입력받은 String $q$ : 초기상태 ($q \in Q$) $F$ : AC를 받는 상태들의 집합($F \in Q$, 여러개 가능) $s$ : Transition Relation DFA와 대부분 같은데 $s$의 의미만 다르다. DFA는 이동할 상태가 결정적이기 때문에 경로가 유일하지만 NFA는 모든 경로로 이동을 할 수 있기 때문에 Relation이라는 용어를 쓰는 것 같다. Problem..

Pigeonhole Principle (비둘기집 원리) Pumping Lemma를 위해 Pigeonhole Principle을 먼저 소개한다. $N+1$개의 변수를 $N$개의 공간에 넣으면 적어도 하나의 공간에 $2$개의 변수가 있다. 너무 당연한 말이라 직관적으로 생각하기 쉽고 간단한 원리이다. 위에서는 $N+1$개의 변수라고 했는데 이를 일반화 할 수 있다. 증명은 여기 Pumping Lemma (for DFA) 여러 종류의 머신에 대한 Pumping Lemma가 있는데 지금 우리는 DFA만 알고 있으니까 DFA용 Pumping Lemma를 알아보자. (튜링머신은 너무 복잡해서 Pumping Lemma를 적용하기 힘들다.) $N$개의 상태를 가지는 어떤 DFA M이 길이가 $N$인 String을 AC..

DFA (Deterministic Finite Automata) 이제부터 전자계산기의 동작을 알아보도록 하자. DFA는 이름에서 알 수 있듯 "결정적인 유한 오토마타"이다. 상태는 유한하고 어떤 상태에서 어떤 입력이 들어오면 이동하는 상태가 정해져있다는 뜻이다. DFA 는 다음으로 이루어져있다. $ M = (Q, \Sigma, q, F, s)$ $Q$ : DFA상태들의 집합 $\Sigma$ : 입력받은 String $q$ : 초기상태 ($q \in Q$) $F$ : AC를 받는 상태들의 집합 ($F \in Q$, 여러개 가능) $s$ : Transition Function 표기법은 책, 자료마다 다르지만 의미는 같다. 지난시간에 본 Problem X1을 DFA로 나타내면 다음과 같다. 여기에서 각 노드(..