CSC363 at UTM - Computability and Complexity - Fall 2009


Lecture: Monday 11 - 13, NE 228
Tutorial: Thursday 11 - 12, CC 2134
Instructor: Avner Magen
Office hours: Monday 14-15 (SB 4062, 905-569-4741).
Tutor: Bryce Zimny

Useful Information/links




Handouts

(all solutions except A3 are avialable!)
  • Assignments
  • Exercises



    • The story of the course so far

  • relevant reading: Section 3.1
  • Our starting point was the pursuit of a mathematiical model that can capture "computation". The grand goal is to say what can be computed and what cannot.
  • We have studied the model called Turting Machine (TM for short). This is a machine that has a finte description, and that seems like an upgraded version of an autmaton, except it that it has read/write access to an infinite tape on which it can "move" back and forth.
  • We saw that there is a Turing Machine that can accept all strings of the form {w#w : w a string of 0/1 } and reject all others. This shows that the model of TM is stronger than that of automata.
  • At tutorial we saw some examples of TM for the language {0^(2^n) : n >0}. This is example 3.7 p143.
  • relevant reading: Section 3.2.
  • We explained the notion of a "configuration" which lets us concisely express a snapshot of the TM during its work.
  • We have discussed the "language" recognized by a turing machine: the set of all strings that the machine accepts. Further we said that if the machine always (on all inputs) halts then the language of the inputs it accepts is decided by it. (Such machines are called "deciders".)
  • Variants of Turing Machines: There are many ways to define variants on Turing machines. Most of them turn out to be equivalent in power to "standard" Turing machines. We have discussed such variants as multitape-TM, and machines with more movement instructions (stay-put).
  • Other variants that were discussed are the machines with doubly infinite tape and ones whose readng head moves a few steps.
  • We saw that all of these models are "equivalent" with the standard model. Showing tht entails showing that the operation any machine from the model of interest cn be simulated with a standard TM, and vice versa.
  • nondeterministic TM are TM that can move to one of a few possible configuration at any given step. Such a machine accepts input x if there is a possible path of transitions (computation path) that leads to an accepting configuration (with state q_{accept}). We show that such machines are also equivalent to simple TM.
  • Enumerators are basically TM that have a special tape, 'printer tape' and a special state PRINT: whenever the machine is at this state, the content of the printer tape is "printed". The language associated with an enumerator is the set of words that are printed. It is also called the language 'enumerated' by the enumerator.
  • We saw that a language is recognizable iff there is an enumerator enumerating it.
  • We mentioned other resonable models, most noteably machines with Random Access Memory, and saw tht all are still equivlent to standrd TM.
  • Church Turing thesis: anything that can be reasonably computed can be computed by a TM.
  • We can now think of TM as general computers. We need some conventions to deal with other input types than strings. So, we will write < G >, for example, for the input string that represent a graph G. Likewise, we can write < M > to mean the (encoding) of a turin machine and so on.
  • relevant reading: Section 4.1, 4.2
  • A useful object we should relate to from now on is a special TM called "universal TM" that when gets as input a machine M and input string ( < M,w > ) what it does is simulate the operation of M on w.
  • We started discussing the possiblity of languages that cannot be decided (undecidable languages) or even recognized (unrecognizable languages).
  • To point to a specific language that is not decidable we considered A_TM = {< M,w > : M is a TM that accepts w}. We showed that is undecidble, as if it were, and H would be the alleged decider, the machine D that on input < M > return the opposite of H(< M,< M > >) would also be a decider. But then we obsrved that this decider cannot exist as there are two inconsistent ways to reason about whether D(< D >) would accept or reject.
  • To build a more complete mathematical basis for the theory of undecidability we discussed the notion of "countable sets": sets whose elements can be "counted". We showed that the set of rational numbers is countable while the set of rela numbers isn't. In order to do this we introduced the method of "diagonalization" due to Cantor.
  • We said that there are uncountable number of languages and only a countble number of turing machines, hence there are languages that cannot be recognized (since every TM recognizes only one lnguage).
  • We saw that other langages can also be shown to be undecidable using the fact that A_TM is undecidable. This is done via REDUCTION. For instance we discussed the language HALT_TM = {< M,w > | M halts on w}. We said that if we were able to decide HALT_TM we would be able to decide A_TM. But the latter is an undecideable language, hence HLAT_TM is also undecidable. More specifically, we *reduce* A_TM to HALT_TM, namely we use a subroutine to solve HALT_TM in order to solve A_TM.
  • Test material will include everything up to now, but for the last class (undecidability of A_TM ad related concepts) for which you haven't received feedback on your work my expectations are not as high as for the other part of the course.
  • relevant reading: Section 5.1
  • we saw other languages are undecidable by reducing A_TM or other undecidable languages to them. These languges were REJ_TM = {< M,w > : M rejects w}, E_TM = {< M > : M doesn't accept any input} and EQ_TM = { < M1,M2 > : L(M1) = L(M2)}.
  • One important construction that we saw was the machine M_w which is a machine that ignores its input and behaves exactly the way M behaves on w.
  • We saw that all of these proofs had similar traits. They all involved two languages, A that we know is undecidable and B that we want to show is undecidable. Now we show that "if B decidable (let H by a hypothetical machine that decides B) then A will be shown to be decidable by coming up with a machine D that uses H as a subroutine and decides A." (This structure is already discussed above for HALT_TM but I am repeating here to make a point about this type of proof).
  • This is a contradiction and we conclude that such an H does not exist and so B is not decidable.
  • But not only that, we saw that the way D is constructed using H, is quite similar across the board. Specifcally, D starts by converting its input x to a string y, and then run H on y. In two of the reductions (REJ_TM and EQ_TM) D does the same as H.
  • relevant reading: Section 5.3
  • To capture these commonalities we introduced the notion of "mapping reduction". A mapping-reduction from language A to a language B is a *computable* function f such that x is in A if and only if f(x) is in B.
  • When we have a function like that we say A <=m B.
  • The imporant theorems regarding mapping reductions is that if we can decide decide B then we can decide A (5.22 in the book). If we can recognize B then we can recognize A (thm 5.28 in the book)
  • It is useful to think of <=m as inequality of hardness, so A <=m B is saying that A is at most as hard as B.
  • Using this, we showed a few reductions that allowed us to conclude the undecidability of the relevant langyages. We saw A_TM <= EQ_TM A_TM <= (E_TM)^c (L^c is the complememnt of L), A_TM <= HALT_TM (example 5.24). This allowed us to deduce that (E_TM)^c, EQ_TM, HALT_TM are undecideable.
  • We saw that if A <=m B then also A^c <=m B^c.
  • We then showed unrecognizability of certain languages. We knew from before that A_TM is unrecognizable. We showed that A_TM <=m E_TM^c and so be the observation in th previous bullet, A_TM^c <=m E_TM, and so E_TM is unrecognizable.
  • We showed that EQ_TM as well as EQ_TM^c are unrecognizable (thm 5.30 in th book). To see the first fact, we showed that E_TM <= EQ_TM (example 5.26), and we have just established that E_TM is unrecognizable. For the second fact, since A_TM <= since A_TM <=m EQ_TM we have A_TM^c <=m EQ_TM^c, and that shows EQ_TM^c is unrecognizable.
  • We mentioned that mapping reducibility is transitive elation: if A <=m B and B <=m C, then A <=m C.
  • Most reduction were quite simple, revolving around ideas like the above, but we also saw a more interesting reduction from HALT^c to ALL_TM that showed the unrecognizability of ALL_TM. Here we mapped to M' where M', on input x, simulates M on w for |x| number of steps and Accepts if M didn't stop before the end of the simulation.
  • We described Rice's thm that pertains to languages that are of the form { : L(M) is ...}. For example { : L(M) = emptyset}, or { : L(M) contains 00 but not 1100}. In general we have to make sure the language is defined by properties of the language rather than the machines themselves, and that the property is not trivail. In other words, some machines will be in the language and some will not.
  • Complexity. Relevant reading: Section 7.1, 7.2
    We started the chapter of complexity. Defined TIME(t(n)): all languages for which there is a TM M that decides L, and such that for input x, M runs in time O(t(|x|)). We saw two theorems relating differnt varaints of TM. (i) a language is decided in time t(n) on a multi-tape TM can be decided in time (t(n))^2 (ii) a language is decided in time t(n) on a nondeterministic TM can be decided in time 2^(O(t(n))) on a deterministic turing machine.
  • To handle this issue of robustness and in order to draw a "simple" line between languages that are efficiently computed and ones which are not, we introduced the class P of polynomially computed languages: P = TIME(n) U TIME(n^2) U ... U TIME (n^k) U ... = U TIME(n^k) where the union ranges over all natural numbers k.
  • Tractability thesis says that the question whether or not a language is in P does not depend on the precise model of computation, as long as it is deterministic.
  • We like to think of P as the class of problems to which we have "reasonable" algorithms.
  • we gave some examples for polytime algorithms, like multiplication, PATH, and explained that the way we show an algorithm is polynomial is by giving an analysis in phases, where each phase is polynomial and the number of phases is polynomial.
  • We sw that the naive algorithms to decide if a number is prime (or equivlently to decide PRIME = { : n is prime} that employs a loop from 2 to n-1 and check whether the loop index divides n is exponential in the size of the input (even though linear in the value of the input).
    TEST 2 will cover all material upto here
  • Looking at some natural problems like INDEPENDENT-SET, CLIQUE, HAMILTONAIN PATH, we noticed that all of them can be easily solved in polynomial time nondeterministically, or alternatively, using a polytime verifier: V is a polytime verifier for L if for all x, if x in L then there is a c such that V(x,c) accept, and if x not in L there is no such c. In addition V runs in polytime in |x|.
  • NP is the class of languages that have polytime verifiers. We show that this class is also the class of languages that can be decided in polynomial time by a *nondeterministic* TM.
  • An example of a verifier for CLIQUE: on input the verifier treats c as a possible clique in G of size k. If c is indeed such a set (this takes no more than n^2 time, where n is the mumber of vertices of G) it accepts, otherwise it rejects. This shows CLIQUE is in NP.
  • coNP is simply the complements of languages in NP. examples: graphs that have no clique of size k. prime numbers.
  • one of the biggest question, perhaps the biggest, in the field of computational omplexity is whether P = NP.
  • polytime reductions are tools to relate different languages in NP. These are the same is the reductions we have seen in the first chapter of the course, except they must run in polytime.
  • we write A <=p B to say that A polytime reduces to B.
  • the main benefit from this concept is that if A <= p B and B in P then A is in P. (compare "in P" to "decidable" or "recognizable" in the computability chapter to see that the concepts are quite similar).
  • a big discovery in the 70s was that there are languages that all languages in NP reduce to them. Such languages are called NP-hard. If they are also in NP they are NP-complete.
  • SAT, the language of satisfiable propostional formuals are an example for a language that is NP-complete. This was the first such example and it was discovered by Stephen A Cook from U of T.
  • In fact we can concentrate on 3SAT, that is the language of CNF formulas in which each clause contains at most 3 literals, and Cook's theorem shows that this special case of SAT is already NP-hard. (CNF form means a conjunction of Clauses, each of which is a disjunction of literals, and a literal is a variable or its negation).
  • By reducing 3SAT <=p A we can now show that A is NP-hard. In the case that A is in NP then we conclude that A is NP-complete.
  • We saw how we can reduce 3SAT to Vertex-Cover and to SubsetSum, and later gave reductions from these languages to other languages in NP, suvch as Independent Set, Clique, Partition, and that way we concluded that all of the above problems are NP-complete. I am attaching a short description of the reduction from SUBSET-SUM to PARTITION.

    Announcements

    Date Announcement(s)
    2/12
    		 Review class tomorrow, 3/12 at 11. Location, SB 3131.
    2/12
    		 Correction to A3, Q2. "Almost-IS = { <G> | G is a graph on n vertices that has an almost-independent set of size k}." Should be "Almost-IS = { <G,k> | ... }"
    22/11
    		 Exercise 5 + Assignment 3 are uploaded.
    17/11
    		 Extension to Ex 4: Monday, Nov 23.
    15/11
    		 Exercise 4 is uploaded.
    11/11
    		 At this point I should have emailed you (or at least your partner and he should have forwared to you in case I didn't have your email) your A2. Email me if for some reason you haven't got it.
    10/11
    		 Alex Hyde, Xiao Feng Zhao, and Michael Bennett. Please email me so I can email you (a scanned version of your) your A2.
    10/11
    		 More questions were added to the sample set of questions for T2.
    7/11
    		 Check out the sample set of questions that will be somewhat similar to the questions on term test 2.
    5/11
    		 Solutions to A1 and exercises are available
    3/11
    		 Make sure you check the clarification page (hints) about A2 that can be found under "assignments"
    28/10
    		 Bryce will hold office hour tomorrow, Thursday right after tutorial (12:00) in my office SE 4062.
    26/10
    		 A2 is uploaded. Final version that includes 4 questions uploaded 6:30PM
    23/10
    		 Exercise 3 is uploaded.
    14/10
    		 Make up class is to be held Wednesday October 21st, 11-13 in Ganita Lab (SE 3023C).
    11/10
    		 Here is a sample set of questions that will be somewhat similar to the questions on the term test.
    7/10
    		 Exercise 2 is uploaded. Tip: Use it to brush up your command in the material. It will help!
    4/10
    		 Check clarifications for A1 (in the assignments page)
    30/9
    		 Bryce will hold office hour tomorrow, Thursday right after tutorial (12:00) in my office SE 4062
    28/9
    		 Extension to A1: Monday October 5 in class. (and to clarify, there are only 3 questions, no more will be added).
    28/9
    		 Check this short following text for some generl clarifications about the material so far.
    23/9
    		 If you don't have the new version of the text check the exercise page for a link to example 3.9 I was referring to in ex1.
    23/9
    		 A1 (in its entirety) is uploaded.
    19/9
    		 The first question of A1 is ready. The rest will be posted soon, but note that for the first you have what you need to start working on it.
    18/9
    		 Exercise 1 is ready. Check the exercises page. All other links (except the assignments link which will have A1 ready later today) are now active.
    17/9
    		 CLASSROOM CHANGE . Our lecture class will be NE228 instead of NE259 as it should be much more suitable for the size of the class. We trade this for this...
    15/9
    		 The page is still under construction. I am expecting all important information to be finlized by Thursday.