NP-completeNP이고 (모든 NP문제) $\le_p$ NPc 인 NPc만약 NPc 중 하나만 poly 알고리즘이 나오면,모든 NP문제는 poly 알고리즘이 있다는 것이 증명된다.$\le_p$ : 다항시간 환원 가능다항시간 함수 $\exists f: \ \sum^* \rightarrow \sum^*$일때,w, $w \in A \Leftrightarrow f(w) \in B$이면 $A \le_p B$라고 한다.-> w가 accept면 reduce된 w가 accept만약 A가 B로 다항시간 환원 가능이고 B가 P에 속하면 A도 P $A\le_pB \ & \ B\in P \Rightarrow A \in P$ 만약 B가 NPc이고 B가 NP인 C로 다항시간 환원 가능이면 C도 NPc이다 B is..

class PSDTM이 다항시간(polynominal time) 안에 문제를 풀 수 있음 $P = \bigcup_{k}TIME(n^k)$ 즉, 시간 복잡도가 O(n), O(n^2), O(n^30), .... 이떄 practicaly solvable하다 한다 PATH problems -> t인 경로가 존재하는가?PATH는 다항시간 내에 풀 수 있는 알고리즘이 있다. $PATH \in P$ 노드가 v개 있을 때, 단순하게 브루트 포스로 풀면... O($v^v$)의 시간복잡도를 갖게 된다. 그러나, BFS로 풀면... 1. s에 .을 찍는다 2. s와 연결된 노드 중 .이 안찍혀 있는 노드는 .을 찍는다 3. 만약 t가 .이 찍혔다면 accept O(V+E) -..

time complexity풀 수 있는가? (decidable / undecidable)-> 그럼 '실제로' 풀 수 있는가? (P / NP) 단순히 풀 수 있다 없다를 넘어현실적으로 시간, 자원 등을 소모하여 풀 수 있겠는가?time complexity theory시간 복잡도를 측정하는 방법BIG-O 표기법(자료구조 1 참고...)-> 이때 기준을 single deterministic TM으로 삼는다 polynominaly diff VS exponetialy diff만약 다항식 형태면 polynominal하게 다르다고 하고equivalent하다고 한다. Single-tape TM VS Multi-tape TMSTM의 시간 복잡도가 O(t(n))이라 해보자.이떄 MTM은 과연 얼마나 걸릴까? MTM -> ..

reducibilityreduction: A문제를 B문제로 바꿔 풀어보자그리고 B문제를 풀 수 있는 방법이 있다면,그 방법으로 A도 풀 수 있을 것이다!예) 곱셈은 덧셈 여러번으로 reduce될 수 있다. 곱셈 -(reduce)-> 덧셈 (sol) A is reducible to B: A가 B로 reduce될 수 있음A ≤ B의 관계A가 B로 reduce 될 수 있고, B가 deciable하면 -> A도 decidable하다. A가 B로 reduce 될 수 있고, A가 undicidable이면 -> B도 undecidable하다.즉, 알려진 문제 -> 새 문제 일때,새 문제는 적어도 알려진 문제보다 같거나 더 어렵다. 예시reduction은 복잡도 이론에서도 쓰임!undecidable의 ..

non-recognizable language몇몇 language는 turing recognizable하지 않다.왜냐하면 language의 개수가 TR보다 많기 떄문이다!TR is countable하나의 TR에는 여러개의 TM이 대응될 수 있다. 즉, 하나의 language를 여러 방식의 TM으로 나타낼 수 있다그러나, 하나의 TM은 여러개의 TR이 대응될 수 없다.-> 즉, |TR| 따라서 |TM|이 countable하면 TR도 countable하다 TM을 하나의 문자열인 으로 인코딩 했다고 하자. ∈ $\sum^*$ 일 것이고 TM ⊆ $\sum^$일 것이다.이떄, $\sum^*$는 유한 길이의 문자 집합이다. 따라서 길이에 따라 정렬 후 자연수와 대응시킬 수 있다. (마치 N진법마냥..

non-TR에 대해 알기 위해선 무한집합의 크기에 대해 정확히 따져볼 필요가 있다! 집합의 크기(자세한건 집합론에서 다루겠다.) 단사: 하나의 input에 하나의 output이 대응됨 $f: \ X\rightarrow Y$에 대해, $x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$ $\Leftrightarrow f(x_1) = f(x_2) \Rightarrow x_1 = x_2$전사: output에 적어도 1개의 input이 대응됨 (치역 = 공역) $f: \ X\rightarrow Y$에 대해, $\forall y \in Y ,\ \exists x \in X, \ y = f(x)$전단사: 전사이며 단사예) y = 4x는 전단사함수이다. -..

undeciablity몇몇 문제들은 알고리즘적으로 풀지 못한다(algorithmically unsolvable)undecidable문제에 대응되는 decider가 존재하지 않는 language A_TM$A_{TM}$: 어떤 turning machine(TM)과 string(w)가 주어졌을 때, 이 TM이 w를 accept할 지 판정하는 문제 $A_{TM}$ = { | M is turning machine that accepts input string w}인코딩된 문자열이 주어졌을 때TM 내부에서 w가 주어졌을 때 M을 시뮬레이션 한다내부 state, 현재 input char 등을 tape에 가록해가며 하면 된다.만약 M이 accept하면 TM도 accept, reject하면 reject한다근데 M이..

decidablity애초에 답이 없는 문제를 풀기 위해 뻘짓을 하는 것만큼 낭비되는 일은 없다.decidabledecider가 존재하는 language decider: loop없이 accept, reject로 결과를 내놓는 TM (계산이론 18 참고)language가 decidable하다는 것은 problem이 decidable한 것을 보이는 것과 마찬가지이다. 다음은 deciable한 language(problem)의 예시이다. A_DFA$A_{DFA}$: 어떤 DFA(D)와 string(w)가 주어졌을 때, 이 DFA가 w를 accept할 지 판정하는 문제 $A_{DFA}$ = { | D is DFA that accepts input string w}인코딩된 문자열이 주어졌을 때 ..

알고리즘여태까지 TM을 배웠는데 이제 실생활과 관련지어 생각해보겠다.(TM) -> (high-level TM) -> (algorithm) -> (program) = (computer) 힐베르트의 10번째 문제임의의 다항식에 대해 정수근을 가지는지 판정하는 알고리즘은 무엇인가? (단, 유한번의 연산으로 판정할 수 있어야 됨)즉, 이 문제는 다항식 정수근 판별 문제가 decidable한지 묻고 있다...recognizer일단 decider보다 더 간단한 recognizer를 만들어보자...임의의 input에 대해 다항식의 문법을 지키는지 검수만약 문법이 옳다면 0, 1, -1, 2, -2, ... 를 순서대로 넣어보며 정수근 찾기-> 만약 정수근이 있다면? 언젠가 멈추고 accept-> 만약 정수근이 ..

여러가지 TM앞에서 본 TM(Deterministic Turing Machine)말고도 여러 TM이 있다.그리고 이 TM들의 power는 전부 같다! stay TMLeft, Right 말고도 제자리에 멈춰있는 Stay가 포함된 TM즉, $\delta : \ Q \times \Gamma \rightarrow Q \times \Gamma \times {L, \ R, \ S}$stay TM = TM 증명TM -> stay TM일반 TM은 stay 기능을 사용하지 않는 stay TM과 같으므로,TM을 stay TM으로 나타낼 수 있다.stay TM -> TMstay 기능을 left, right만 있는 TM에서 구현하는 법은tape과 state에 아무 변화도 주지 않고left, right 1번씩 하는 것이다.즉,..

Turing machinetape: PDA의 input과 stack 역할control: state diagram특징무제한 메모리 용량PDA의 stack마냥 메모리가 무한하다무제약 메모리 접근PDA는 stack이라 맨 윗부분만 접근 가능했지만,TM은 어느 곳이든 head를 옮겨 데이터를 읽고 쓸 수 있다.accept, reject, loopaccept, reject state에 도달만 하면 바로 accept, reject그리고 accept, reject에 도달하지 못하고 반복하는 loop가 존재할 수 잇다. 수학적 정의정의 ($Q$, $\sum$, $\Gamma$ $\delta$, $q_0$, $q_{accept}$, $q_{reject}$)$Q$: 상태의 유한 집합$\sum$: input alphabet..