Discrete Math II Howon Kim 2019. 11

Agenda 1 Automata Theory 2 Regular Expression & Regular Languages 3 Finite Automata DFA(Deterministic Finite Automata) FA Applications 4 Non-deterministic Finite Automata 5 Grammars & Languages 6 Theory of Computations

Overview Set Theory of Strings (Chapter 6.1) Regular Expressions & Regular Languages Finite State Machines Deterministic Finite Automata (DFA) Non-deterministic Finite Automata (NFA) Grammars and Languages Types of Grammars and Languages Associated Machines including Turing Machine Computation Theory NP Problem

Computation Model Turing Machine : tape Finite control Deterministic / Non-deterministic

Complexity Two kinds of Complexity Polynomial Time (or Space) Time Complexity total amounts of state transitions (instructions) - the number of operations or running time needed, using the size of the input as its argument Space Complexity total amounts of space - A measure of the amount of computational space needed in the execution relative to the size of the input Polynomial Time (or Space) Time (or Space) Complexity : O(nc) - c is constant Exponential Time (or Space) Time (or Space) Complexity : O(2nc)

Classes P class PSPACE class EXP class 모든 입력에 대하여 polynomial time 내에 halt하면서 언어 L을 determine하는 TM이 존재하면, L  P. - The complexity class P contains every language that can be decided by a deterministic TM with polynomial time complexity. PSPACE class 모든 입력에 대하여 polynomial space 만을 사용하면서 언어 L을 determine하는 TM이 존재하면, L  PSPACE. - The complexity class PSPACE contains every language that can be decided by a deterministic TM with polynomial space complexity EXP class 모든 입력에 대하여 exponential time 내에 halt하면서 언어 L을 determine하는 TM이 존재하면, L  EXP.

Relation among classes (1) P  PSPACE Polynomial time 내에는 polynomial space 이상을 사 용할 수 없다. PSPACE  EXP Polynomial space를 사용하면서 만들어지는 TM의 모든 configuration은 exponential 하다. P  PSPACE  EXP

NP Class Definition of NP Class Non-deterministic Turing Machine Non-deterministic Polynomial time Definition of NP Class 모든 입력에 대하여 polynomial time 내에 halt하면서 언어 L을 determine하는 Non-deterministic TM이 존재하면, L  NP class. Non-deterministic Turing Machine A parallel Turing machine that can take many computational paths simultaneously Non-deterministic Turing Machine is like a deterministic TM, except that the transition function:  : a subset of ( (Q-H) )  ( Q{L,R,S} )

NP Class Intuitively, NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes". More precisely, these proofs have to beverifiable in polynomial time  In an equivalent formal definition, NP is the set of decision problems ”solvable” in polynomial time by a non-deterministic Turing machine. The equivalence of the two definitions follows from the fact that an algorithm on such a non-deterministic machine consists of two phases, the first of which consists of a guess about the solution, which is generated in a non-deterministic way, while the second consists of a deterministic algorithm that verifies or rejects the guess as a valid solution to the problem. http://en.wikipedia.org/wiki/NP_(complexity) NP는 대답이 "예"인 사례가 그 대답이 실제로 "예"라는 사실을 효율적으로 증명할 수있는 모든 결정 문제의 집합임

Relation among classes (2) P  NP, since L(DTM)  L(NTM) NP  PSPACE 어떤 NTM도 Polynomial time내에는 polynomial space 이상을 사용할 수 없다 P  NP  PSPACE  EXP

P vs. NP P versus NP problem Cook’s theorem : SAT  P  P = NP ? 현실에 존재하는 대부분의 문제는 P class or NP class에 속한다. P = NP ? Very important Open Problem If P and NP are not equivalent, then the solution of NP-problems requires (in the worst case) an exhaustive search, while if they are, then asymptotically faster algorithms may exist. The answer is not currently known. In a 2002 poll of 100 researchers, 61 believed the answer is no, 9 believed the answer is yes, 22 were unsure, and 8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove Cook’s theorem : SAT  P  P = NP ?

NP-hard NP NP-hard (NP 만큼 어렵다) L  A problem is NP-hard if an algorithm for solving it can be translated into one for solving any other NP-problem ( NP class). NP에 속하지 않고 P problem에 속하는 NP-hard 문제도 존재함(예: Halting Problem) It is much easier to show that a problem is NP than to show that it is NP- hard. 변형은 가능하지만, NP에 속하는지 증명하지 못함 NP : Non-deterministic algorithm in Polynomial time hard : as hard as any problem (the hardest problems) in NP L NP Reducible Polynomial Time NP-Complete Problem

NP-complete Def. of NP-complete Examples L  NP class and L  NP-hard NP-Complete Problem: A problem which is both NP (verifiable in nondeterministic polynomial time) and NP-hard (any NP-problem can be translated into this problem). Examples of NP-hard problems include the Hamiltonian cycle and traveling salesman problems. Examples CNF satisfiability (Cook Theorem), 0/1 Knapsack, Hamiltonic-cycle, Traveling Salesperson, Clique decision, etc. 변형 가능함 해가 주어졌을때, polynomial time내에 그 해가 yes라는 것을 결정할 수 있음 NP : Non-deterministic algorithm in polynomial time Complete : solve one, solve them all..

Example of NP-complete How to know another problem, A, is NP-complete? - To prove that A is NP-complete, reduce a known NP-complete problem to A Requirement for Reduction - Polynomial time - YES to A also implies YES to SAT, while No to A also implies No to SAT (Note that A must also have short proof for YES answer) reduction in P(n) solve A SAT A YES/NO

Cook Theorem 참고) Design and Analysis of Algorithms by V.V. Muniswamy, p.186~187

Cook Theorem 참고) Design and Analysis of Algorithms by V.V. Muniswamy, p.186~187

Cook Theorem Cook–Levin theorem(Cook's theorem) states that the Boolean satisfiability problem is NP-complete An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem. That is, All problems in NP reduce to SAT (an example of NP-complete problem) If we can solve SAT, we can solve any of them NP-complete 문제는 거대한 군을 이루며, 서로 논리적 연결관계를 가지고 있음. 이 때문에, NP- complete중에서 한 문제를 (현실적 시간에)풀면 다른 문제도 쉽게 풀림(아직 이 문제에 대해 현실적 시 간(polynomial time)에 풀 수 있는 방법은 존재하지 않음) Cook Theorem은 SAT문제는 NP-complete이라는 것을 증명하는 정리로서, 모 든 NP 복잡도에 속하는 결정 문제는 polynomial time내에 SAT문제로 변환가 능함을 의미함 The question of whether such an algorithm exists is called the P=NP problem and it is widely considered the most important unsolved problem If there is an efficient algorithm for SAT, then P=NP

Some definitions on CNF, SAT, etc. 2-clause: (y∨z), k-clause: (y1∨…∨ yk) A CNF(Conjunctive Normal Form) is a conjunction(AND) of clauses. Every Boolean formula can be represented by a conjunctive normal form. A CNF F is satisfiable if F is true, that is, there is x∈{0,1}n such that F(x)≠0. The satisfiability problem is NP complete. 3-SAT formula (y1∨z1∨w1)∧…∧ (ym∨zm∨wm) k-Satisfiability problem (SAT problem) Input: k-SAT formula Problem : is the formula satisfiable ? Output : yes or no Cf. POS(Product of Sum)

SAT Problem SAT : CNF Satisfiability problem Reducibility : L1  L2  Deciding whether a given Boolean formula in conjunctive normal form (CNF) has an assignment that makes the formula "true." (어떤 CNF 논리식을 참으로 하는 논리변수 값이 존 재하는가?)  SAT  NP class & L ( NP class)  SAT Reducibility : L1  L2  If problem L1 is mapping reducible to problem L2, if problem L2 has been previously solved, then we can obtain a solution to problem L1  An algorithm for solving L2 can be translated into one for solving L1 in polynomial time  Solving L2 is at least as hard as solving L1

Summary : P, NP, NP-hard, NP-complete Polynomial time내에 yes/no를 대답할 수 있으면 P We say that a decision problem belongs to the class P if there is an algorithm A and a number c such that for every instance I of the problem the algorithm A will produce a solution in time O(B c), where B is the number of bits in the input string that represents I. NP Non-deterministic polynomial Yes인 해를 제공했을 때, yes라는 대답을 내는 해라는 것을 polynomial time 내에 확인 가능하면 NP NP is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information. So we aren't asking for a way to find a solution, but only to verify that an alleged solution really is correct.

Summary : P, NP, NP-hard, NP-complete 다음 조건을 만족하는 어떤 문제 L은 NP-hard이다 모든 NP문제가 문제 L로 polynomial time에 변환 가능한 L 또한, 알려진 HP-hard 문제 A로부터 문제 L로 polynomial time에 변환 가능 한 L NP-hard는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이다. 다시 말하면, NP-난해(hard)는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다. 다시 말하면, NP-hard는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다. 다음 조건을 만족하는 어떤 문제 L은 NP-complete이다 어떤 문제 L이 NP이고 L이 NP-hard일 경우 NP-complete은 NP-hard의 일부 즉, NP-complete은 NP-hard 중에서 NP인 문제들의 집합이다.

P and NP P=NP NP P (a) (b) We don’t know if (a) is true or (b) is true !

NP와 NP-Complete, NP-Hard의 관계 SAT We assume P  NP NP-hard 문제 중에서 NP인 문제들의 집합이 NP-complete인데, NP-complete을 P에 풀면 P=NP이고 반대로 풀수 없다는 것을 확인하면 P!=NP가 됨.

Write-only output tape Computation Model RAM (Random Access Machine) Load/Store, Add/Sub/Multi/Div, Read/Write, Jump, Halt Unit time의 operation으로 간주하는 theoretical model Program Accumulator Location counter Write-only output tape Read-only input tape