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}인코딩된 문자열이 주어졌을 때 ..