南京大学：Decidability、Complexity（P、NP、NPC）、Reduce（P NP NPC）

大房 NANJING UNIVERSITY Decidability The diagonalization method The halting problem is undecidable

The diagonalization method The halting problem is undecidable Decidability

Undecidability decidable all languages reqular languages context free languages RE decidable cre c all languages our goal. prove these containments proper

Undecidability decidable  RE  all languages our goal: prove these containments proper regular languages context free languages all languages decidable RE

A Countable and Uncountable Sets the natural numbers n=(1, 2, 3, .. are countable Definition a set s is countable if it is finite. or it is infinite and there is a bijection f:N→S

Countable and Uncountable Sets ◼ the natural numbers N = {1,2,3,…} are countable ◼ Definition: a set S is countable if it is finite, or it is infinite and there is a bijection f: N → S

Example Countable set The positive rational numbers Q=m/n m, nEN) are countable Proof 11/21/3141/516 212/22/3242/526 3/13/23/33/43/536 4/14/24/3444/54/6 5/1

Example Countable Set ◼ The positive rational numbers Q = {m/n | m, n  N } are countable. ◼ Proof: 1/1 1/2 1/3 1/4 1/5 1/6 … 2/1 2/2 2/3 2/4 2/5 2/6 … 3/1 3/2 3/3 3/4 3/5 3/6 … 4/1 4/2 4/3 4/4 4/5 4/6 … 5/1 … …

A Example Uncountable Set Theorem: the real numbers r are not countable(they are uncountable) How do you prove such a statement? o assume countable(so there exists bijection f) o derive contradiction(some element not mapped to by f o technique is called diagonalization( Cantor)

Example Uncountable Set Theorem: the real numbers R are NOT countable (they are “uncountable”). ◼ How do you prove such a statement?  assume countable (so there exists bijection f)  derive contradiction (some element not mapped to by f)  technique is called diagonalization (Cantor)

A Example Uncountable Set Proof o suppose R is countable o list r according to the bijection f: n f(n 13.14159 25.55555. 30.12345 40.50000

Example Uncountable Set ◼ Proof:  suppose R is countable  list R according to the bijection f: n f(n) _ 1 3.14159… 2 5.55555… 3 0.12345… 4 0.50000… …

A Example Uncountable Set Proof o suppose R is countable o list r according to the bijection f: set X=0. a1a2a3a4 13.14159 where digit a; t ith digit after decimal 25.55555 point of f((not 0, 9) eg.x=02312. 30.12345 x cannot be in the list 40.50000

Example Uncountable Set ◼ Proof:  suppose R is countable  list R according to the bijection f: n f(n) _ 1 3.14159… 2 5.55555… 3 0.12345… 4 0.50000… … set x = 0.a1a2a3a4… where digit ai ≠ i th digit after decimal point of f(i) (not 0, 9) e.g. x = 0.2312… x cannot be in the list!

Non-RE Languages Theorem: there exist languages that are not Recursively enumerable Proof outline o the set of all tms is countable o the set of all languages is uncountable o the function L: TMS)languages cannot be onto

Non-RE Languages Theorem: there exist languages that are not Recursively Enumerable. Proof outline:  the set of all TMs is countable  the set of all languages is uncountable  the function L: {TMs} →{languages} cannot be onto

Non-RE Languages Lemma the set of all tms is countable Proof o the set of all strings 2* is countable for a finite alphabet 2. With only finitely many strings of each length, we may form a list of 2* by writing down all strings of length 0, all strings of length 1, all strings of length 2, etc o each tM M can be described by a finite-length string s o Generate a list of strings and remove any strings that do not represent a TM to get a list of TMs

Non-RE Languages ◼ Lemma: the set of all TMs is countable. ◼ Proof:  the set of all strings * is countable, for a finite alphabet . With only finitely many strings of each length, we may form a list of * by writing down all strings of length 0, all strings of length 1, all strings of length 2, etc.  each TM M can be described by a finite-length string s  Generate a list of strings and remove any strings that do not represent a TM to get a list of TMs

Non-RE Languages Lemma: the set of all languages is uncountable Proof o fix an enumeration of all strings S,, S2, S3 (for example, lexicographic order) o a language L is described by its characteristic vector xu whose ith element is0 if s: is not in l and 1 if s; is in l

Non-RE Languages ◼ Lemma: the set of all languages is uncountable ◼ Proof:  fix an enumeration of all strings s1 , s2 , s3 , … (for example, lexicographic order)  a language L is described by its characteristic vector L whose ith element is 0 if si is not in L and 1 if si is in L