나름 개발자의 IT블로그

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로 나타내면 다음과 같다. 여기에서 각 노드(..

지난시간은 집합을 배우고 이젠 또 이상한걸 배우네요. 암호는 언제 배우죠? 암호랑 상관이 없어보이는 내용이 이어지는 것 같다. 하지만 이 모든 것들이 암호의 본질에 대해 필요한 내용들이니 알아보도록 하자. Language 튜링머신(컴퓨터)이 해결하는 문제를 나타낸다. 용어부터 정의하고 가자. Symbol : 단순 문자 (0,1,a,b,c, ...) String : 길이가 유한한 Symbol의 배열 (01010, ababc, 00a1b, ...) $\lambda$ : 길이가 0인 String Alphabet : 길이가 유한한 Symbol 집합이고 $\Sigma$로 나타낸다. ({0,1}, {a,b,c, ..., z}) Language : String들의 집합 ({$\lambda$, 0, 1, 01, 10,..

Countable vs Uncountable 위 용어를 의미로 해석하면 "셀 수 있는"과 "셀 수 없는"이다. 셀 수 있다는 의미로 접근하면 Countable Set은 유한집합을 의미할 것 같다. 하지만 유한집합은 Finite Set이라는 용어가 있고 이는 Countable Set과 구분되고 심지어 위 두 용어는 모두 무한집합(Infinite Set)에서 정의한다. Countable Set은 자연수집합과 대응되는 집합이다. 자연수가 개수를 세는데 사용되니 이런 의미를 가지게 된 것 같다. 앞에서 보였듯이 $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|$이므로 $\mathbb{N},\mathbb{Z},\mathbb{Q}$는 모두 Countable Set이 된다. 반면 $\mathbb..

원소의 개수를 세자 어떤 집합의 원소의 개수를 Cardinality라고 하고 기호는 $|A|$로 나타낸다. (앞으로 크기라고도 표현할 것이다.) Cardinality에 관해 두가지 성질이 있다. $|A| < |B| < |C|$ 이면 $|A| < |C|$이다. $|A| = |A|$이다. 당연해보이지만 일단 짚고 넘어가자. 유한집합에서 Cardinality는 그냥 원소의 개수를 세면 되기 때문에 생각하기 쉽다. 하지만 집합이 무한집합이라면 어떨까? 일반적으로 생각하기 힘들다. 자연수 집합 $\mathbb{N}$이 있다. $\mathbb{N}$는 무한함이 자명하다. 자연수에 0을 추가해 새로운 집합 $\mathbb{N}^+ = \mathbb{N} \cup \{0\} $을 정의하자. (범자연수 집합이 된다.) ..