CSC363 - Computational Complexity and Computability (Summer 2005)

Previous versions of this course:

• CSC 363 taught by Paul McCabe in winter 2005. He has posted nice lecture notes that I sometimes follow. However, there will be differences in what I'm doing.
• CSC 363 taught by Francois Pitt in fall 2004. He also has lecture notes I will be looking at.
• CSC 365 taught by Prof. S. A. Cook in fall 2004. This is a more advanced version of CSC 363, and it might touch on subjects we will not consider. I'm giving you the link as you might want to check out old assignments and solutions.

Because of future versions of the course, I removed the solutions from the webpage. If you really need them, come see me in my office.

Week 13
Here are the slides I used this week: [ps] [pdf].
The FPTAS for MAX-GK appears in Paul's lecture notes on "Approximation Schemes".

Here is the solution to Assignment 4: [ps] [pdf].
I've put in many more details than I expected from you. There was a problem about k-SKD, explained in the solutions at the end. If you dealt with it, you'll get 3p bonus. If not, you won't lose marks. Note, you still have to have dealt with the "regular" case.

Here are some comments regarding the marking of Assignment 3: [txt]. The TA who marked this assignment will be in regular office hours this Thursday if you have questions about marking.

Week 12
Here are the slides I used this week: [ps] [pdf]. The Powerpoint to ps and pdf translation is giving me headaches. Let me know if you have troubles reading them.
The material is compiled from various sources, like Francois' lecture notes, Paul's lecture notes, and the books. Both approximation results (Vertex Cover and TSP) appear in the last chapter of CLRS. I think the Vertex Cover result also appears in Sipser 10.1. If you want to have a look at the TSP result and you don't have CLRS, it's also covered by Paul in his lecture notes.

I've updated Assignment 4: [ps] [pdf].
The main differences are that in question 3a, I'm only asking for the maximum weight that you can get, not for the set achieving it. For question 3b, you may perform divisions involving weights.
I posted it on July 28th, and it is due on August 9th, before lecture. For policies on lateness and collaboration, check the main course web page.

Notes on Assignment 4:

• For question 1, I realized that we don't really need the definition of coNP-complete, but I'll leave it there for reference. This question should be easy.
• In question 2, you have to choose what hard language you want to solve using CNF₃. I suggest you try something about propositional logic, the ones we've seen include SAT, 3-SAT and CNF-SAT. I also suggest you first figure out how the reduction should work, and only afterwards decide which of these you need to pick. Inside the reduction, if you notice that some variable x appears 100 times in the formula on the right, you must do something about it, like for instance introducing new variables y to cover its occurences. What is important is to realize how to do it so that the original formula is satisfiable IFF the new one, with at most three occurrences of each (new) variable, is satisfiable. The idea is to enforce this behaviour in the new formula by including clauses which force the new variables to take the same truth value in any satisfying assignment. For example, if you want to introduce two variables p and q, and you want them to have the same truth value in a satisfying assignemnt, include the clauses (not p OR q) AND (not q OR p). These are saying that p implies q and q implies p, which means p is equivalent to q. Note that this construction already consumed 2 of the 3 possible occurences of either p or q.
• For Question 3a, I just want you to find the maximum weight you can pack without exceeding the capacity. You can also find which items you need to pack, but the question was supposed to be only 5p.
• For question 3b, I can tell you that at least one of those languages in NP-complete. I changed the handout to allow for rational numbers, because in one of the problems you must scale the weights, and this requires rationals. Regarding k-SKD, somebody pointed out that if k=0, then the problem is equivalent to SUBSET-SUM. This is not a complete solution. What I need you to do is to show what happens for any k. Maybe for any k, the problem is NP-complete. Maybe for any k>=1, the problem is in P.
• Another note about k-SKD. You have to realize that k is part of the problem definition, while W (the capacity) is part of a certain instance. If you start with k=5000, and you get an instance with W=1000, the condition requires you to say whether you can hit any sum between -4000 and 1000 using the positive rational weights. You can always do this by not packing anything in the knapsack (i.e. S is the empty set), which achieves weight 0. You shouldn't be bothered by this fact, though. For any fixed k, there will be non-trivial instances.
• For the entire question 3, I'm excluding negative or zero weights. I've heard that maybe if we allow them, some question is easier. I have yet to see that solution. However, the reason I'm excluding them is that I'm trying to keep it real. I mean, if you have to pack as many boxes in a truck which has a given capacity, you don't usually concern yourself with negative weight boxes.

Week 11
This week, we've seen two of the difficult reductions, 3-SAT to HAM-PATH and 3-SAT to SUBSET-SUM. This concludes the list of "hard" reductions. You can review the details in section 7.5 in Sipser. Next week, we will talk about how to deal with NP-completeness, including basic approximation algorithms. These appear in section 10.1 in Sipser, and also in the last chapter in CLRS.

If you ever doubted that NP-completeness is encountered in practice, check out this page. This link is provided for fun.

Here is the solution to Assignment 3: [ps] [pdf].
I expect to return Assignment 3 in the last lecture.

Week 10
This week, we finished the polytime reduction from CNF-SAT to 3-SAT. Then, we saw a polytime reduction from 3-SAT to CLIQUE, showing that CLIQUE is NP hard. Finally, we talked about the Cook-Levin Theorem, and the general structure of the proof that any NP language is polytime reducible to SAT. Details for these proofs are in the book. A very good reference are also Steve Cook's lecture notes on NP and NP completeness, available on his course webpage.

The course drop date is this coming weekend. I will try to be around my office most of the time, so that you can drop by to talk about your concerns with the course. Send me an email if you know when you want to meet, preferably with several time options, and I will pick one.

Here are some marking comments on Assignment 2: [txt]. Although I expected Enping to have office hours next Tuesday, he will hold them this Thursday, so that you can get remarks if you need them before the drop date. He will be in the regular office hour room in BA.

Notes on Assignment 3:

• For question 1, all that you need is the definition of NP, and the definition of polynomial time reducibility. We've seen two definitions of NP in class. Since this question is concerned with NTMs, I suggest you use the one which talks about NTMs. You can find the proof that U is in NP on Paul McCabe's page, as solution to tutorial exercise 6.
• Question 2a is supposed to be simple. A couple of weeks ago, you have seen in tutorial a proof that a certain restriction of CLIQUE is polynomial. The question on this assignment has a small twist to it, but it shouldn't be difficult to notice it.
• For question 2b, I expect you to give a verification algorithm which takes a string w and a certificate c, and accepts iff w is not in L₂. There are a number of reasons why w would not be in that language. For some of them, you don't even need a certificate to check it. For others, you do need the certificate. A small note about running time. Correction to what I wrote here earlier: The real set of minimal vertex covers of a graph, call it H, can be exponential in the number of vertices in the graph. Think of n vertices, with edges 1-2, 3-4, and so on. The number of minimal vertex covers is 2^n/2. However, this shouldn't be a problem. You must write an algorithm which works in time polynomial in the size of your input, which is G plus F. In particular, H is not part of the input, and you can't assume that the size of H is polynomial in those of G and F.
• For question 2c, you have seen in tutorial how to find a clique if you can use a polytime solver for the CLIQUE decision problem. By the way, this appears in Francois' lecture notes for week 10. For your assignment, you're supposed to do something similar, except that we're dealing with vertex covers. Regarding the invariant, I'm only asking that you give me some justification why your algorithm should work - I'm not asking for a formal proof. I've seen at least one kind of wrong argument from students in office hours. Suppose you know that G has a vertex cover of size k. You can't just check all subsets of that size, since k might be near n/2, so that the number of these subsets is not polynomial in n.
• As to question 2d, the reduction from IS to Half-IS seen in tutorial should be extremely relevant. For your information, you can review it in Steve Cook's solution to Assignment 4, problem 1d. For our assignment, you're dealing with vertex covers, but the proof should go along those lines. One incorrect argument that I've heard is that maybe you don't need to treat both cases, when k is small and k is large. This is incorrect, as one of the directions in your IFF proof will not work.

Week 9
This week in lecture, we talked about polynomial time reductions. We saw that if A is polytime reducible to B and B is in P (resp. NP), then A is in P (resp. NP). In order to formalize our intuition to search for the "hardest" problems in NP, we introduced the notions of NP-hard and NP-complete problems. We saw that deciding whether an NP-complete problem has a polynomial time algorithm is equivalent to deciding whether P=NP. We then introduced a number of notions related to boolean formulas, and defined the languages SAT, CNF-SAT and 3-SAT. We started proving a polytime reduction from CNF-SAT to 3-SAT. This material appears in Sipser 7.4 and 7.5. The reduction we were talking about is given in Francois' lecture notes for week 8. For the Complexity part of our course, chapter 34 of Cormen, Leiserson, Rivest and Stein is also very relevant.

Here is an updated version of Assignment 3: [ps] [pdf].
The main difference with the original version is that I am explicitly asking you to only talk about vertex covers, and not about cliques and/or independent sets. I posted it originally on July 7th. Due to a number of reasons, I will push back the due date by a week. So Assignment 3 is now due on July 26th, before lecture. For policies on lateness and collaboration, check the main course web page.
Note: University regulations require that assignments be collected during the term. As a result, I cannot push back the due date for Assignment 4, which means you will have exactly two weeks to work on it. Please schedule your work load accordingly. At this time, you should be able to do most of Assignment 3, except possibly 2c. You may turn it in early.

Here is the solution to the midterm: [ps] [pdf].
I will take questions about the midterm during regular office hours on Thursday, July 14th.

Week 8
Here is the solution to Assignment 2: [ps] [pdf].

This week in lecture, we introduced the complexity class NP, by giving two characterizations, one involving non-deterministic TMs, the other involving polynomial time verifiers. We've seen that the two definitions are equivalent. We've also seen an example of a problem in NP that is not known to be in P, namely HAM-CYCLE. In the end, we gave informal descriptions of P, NP and coNP, and we presented the "views of the world" - the possible relations between these classes. All this material is in 7.3 in Sipser. Next week, we will talk about polynomial time reductions and NP-completeness, found in 7.4. We might also see material from 7.5.

Week 7
This week, we talked about the difference in time complexity between various models of computation, multi-tape vs single tape TMs and non-deterministic vs deterministic TMs. We introduced and talked about P and the tractability thesis. This corresponds to sections 7.1 and 7.2 in Sipser. The midterm will cover everything we did in class or tutorial, up to and including P (7.2). Specifically, NP (7.3) will not be on the midterm. I might, however, ask you about non-deterministic TMs.

Regarding Assingment 1: Nazanin will hold office hours about marking questions on Tuesday, July 5th, 4pm, in SF3207. This will be just before the midterm, and the office hour is NOT about the midterm. I will ask her NOT to answer any such questions.

Regarding Assignment 2: it is due on Monday, July 4th, and 9pm sharp. You may submit it in the course drop box in BA2220. We've also set up a drop box at UTSC, on the 6th floor of the S-wing, next to the elevator. I will post solutions on Monday shortly after 9pm.

Regarding the midterm:

• If you have questions, I will hold regular office hours on Thursday.
• Midterm will be held in our lecture room, 6-7pm on Tuesday, July 5th.
• I will lecture 7-9 that day.
• The material will be everything up to and including P (7.2).
• The course pages I linked to my webpage are very relevant. From Steve Cook's course, most important are homework and test solutions. From Francois Pitt's course, you can see his assignments and his midterm, but no solutions are provided. From Paul McCabe's course, check out assignment (sometimes with solutions) and the solution to the midterm.
• This is a theoretical course, so I may ask you about definitions.
• There will be 3 or 4 questions, the first one multiple-choice, about true/false, decidable/undecidable, that kind of thing.
• No cheat sheet or other aids.

Week 6
This week, we finished the Computability chapter, and started talking about Complexity. I first presented Rice's Theorem, together with several applications and several instances where it cannot be applied. We then saw how the proof goes in one of the two possible cases, and argued the other case is treated similarly. The full proof appears in Paul McCabe's lecture notes 9. I then spent quite a bit of time talking about why this material is important, with implications regarding such things as perfect virus checkers and debugging.

We started talking about Complexity, which is chapter 7 in Sipser. We defined worst-case time complexity of a machine, and we considered two machines, in different models, both deciding the language {0^k1^k : k>=0}. We saw a regular, single tape TM which needs O(n²) time, and a two-tape TM which needs only O(n) time, suggesting that the choice of a particular model affects the time required to solve a certain problem. Next week, we will make this intuition more formal, reading from sections 7.1 and 7.2.

I haven't been able to return Assignment 1 this week, and as a consequence, I will move back the due date for Assignment 2. Under no circumstances will the midterm date be changed. In class, we agreed to have Assignment 2 due on July 4th, the Monday just before the midterm, at 9pm sharp. I will post solutions shortly after I collect the assignments.

Notes on Assignment 2:

• The point of question 1 is to show that you understand how to develop a diagonalization argument. I've got a lot of questions from students asking if the argument should work for all t, or just for one t. To answer this concern, consider the following statement: "for every integer a, there exists an integer b such that b>a and b is prime". To prove it, you start by saying "let a be a fixed integer", and the remainder of your argument works for that particular a. Similarly, in question 1, I'm asking for a language L which is dependent on t. So, when t=2, L will be some language, when t=500, L will be some other language, and so on. I am NOT asking for a language L which works for all t, the same way as the problem mentioned above is not asking for a prime number b which works for every a. To answer this problem, you have to do three things. (1) given t, build the table and define the language L based on that table; (2) show L is decidable; and (3) show that L is not decidable with lag t. Only parts (1) and (3) are related to the table we define. Overall, or at least once you get it, Question 1 should be easy!
• The point of question 2 is to show that you understand what it means for a function to be computable. One thing I want to point out, as it might not be clear: given the encoding of some TM M, you can always compute its index in the original listing, the one containing all TMs. For this question, I suggest you assume f is computable, and show that under that assumption you can "solve" a problem that you know is "unsolvable".
• For question 3, you don't have to prove things we've seen in class or in the book. Just quote whatever results you need.
• Question 4 should be very easy once you understand mapping reductions.

Week 5
Here is Assignment 2: [ps] [pdf]. I posted it on June 15th, and it is due on June 28th, before lecture. For policies on lateness and collaboration, check the main course web page.

In lecture, we continued talking about how we can show that a problem B is hard by reducing another known hard problem A to B. We defined the notion of computable function, and we showed how the absence of this notion allows us to derive potentially contradicting statements using the construction in question 4a of assignment 1. In the process, we showed that the function which maps every positive integer k to a decider M_k for the set of strings of size at most k in A_TM^c is uncomputable.

Equipped with the idea of computable function, we introduced the notion of mapping reducibility. We saw that if A is mapping reducible to B and A is undecidable, then B is undecidable; and if A is unrecognizable, then B is unrecognizable. We defined INF_TM as the set of encodings of TMs which accept an infinite language, and we showed that both this set and its complement are not recognizable by reducing A_TM^c to both.

Week 4
Here is the solution to Assignment 1: [ps] [pdf]. I plan to return it two weeks after it was due, that is, on June 21st.

This week in lecture we went over the diagonalization method from 4.2 in Sipser, defining what it means for two infinite languages to have the same size, defining what countable sets are, and showing that the set of real numbers is uncountable. We returned to the course material and showed by diagonalization that the set of all languages over a finite alphabet is uncountable, while the set of all TMs (and thus of recognizable languages) is countable. This shows that there are unrecognizable languages. We argued that this fact remains true even if one does not believe the Church-Turing thesis, as long as every "algorithm" has a finite representation. We went on to show how the proof that A_TM is undecidable can be seen as a diagonalization argument.

We then started to talk about reductions, a general procedure in which we assume that we can solve a certain problem B and we show how to solve another problem A. In our case, we reduced A_TM to E_TM. Since the former is provably undecidable, we concluded that the later is also undecidable. We will continue talking about reductions next week. This material is in chapter 5, sections 5.1 and 5.3, in Sipser.

Week 3
In this week's lecture, we first proved that we can assume, without loss of generality, that the input alphabet of a TM contains only 0 and 1, and that its tape alphabet contains only 0, 1 and blank. We went on to talk about a specific way to encode a general TM into a string of 0s and 1s. We then defined the language A_TM and we explained in detail how the "universal" TM U recognizes this language. All this material can be found in Paul McCabe's lecture notes 4. Go look it up if things are still unclear.

The last thing we did in lecture was to prove by contradiction that A_TM is not decidable. This argument can be found in section 4.2 of Sipser, specifically on p.165 (in the first edition). Don't worry about "The Diagonalization Method", we haven't covered it yet.

Notes on assignment 1:

• I have modified question 4 slightly. Since I haven't had time to present in lecture a language that is not recognizable (e.g. the complement of A_TM), I changed part (a).
• Question 1: You are not allowed to assume there is a special delimiter in the input string between the two w's - part of the job of your TM is to correctly break the string in two equal parts.
• Question 1: When I asked you to include informal descriptions of the states, I meant that you should give the person marking some pointers as to how everything is put together. If your TM works in "stages", it might be enough to explain what every such stage is doing. Making the marker's job easier will benefit you, as he/she might reward you for not having to decipher huge state tables/diagrams from scratch.
• Question 3: The material covered in tutorial this week might prove relevant for this question.
• Question 4(a). To show a language is recognizable, give a TM accepting it. Your TM may "use" any of the machines M_i deciding the original languages.
• Question 4(b). To answer negatively, give a TM deciding A. To answer positively, define the languages A_i in such a way that every one of them is decidable, yet A is provably not decidable.
• Question 4(c). The characters in w must appear consecutively in Pi.
• There are three types of terminology for describing Turing Machines: formal description, implementation description and high-level description. Read about them in section 3.3 in Sipser, on pp.144-145 (first edition). Give a formal description for Question 1. Give an implementation description for Question 2. Give high-level descriptions for Questions 3 and 4.

Week 2
Due to unforseen circumstances, the TA assignment for the first week had to be changed drastically. One of the original four TAs was moved to another course, and another one is sick. This leaves us with only two TAs available this week, and three in general. See administrative page for details.

This week in lecture, we began by defining TM configurations and what it means for a configuration to yield another configuration. We went on to define the language recognized by a TM. After introducing the terms Turing-recognizable and Turing-decidable and their equivalents, we saw a couple of tricky examples of decidable languages. The one about the decimal expansion of Pi appears in Francois' first assignment. I said I was ruining a good assignment question, but I did manage to salvage something out of it (see Assignment 1). We talked about several variants of Turing Machines, including one-way infinite tapes, stay-put transitions, multiple tapes and nondeterminism. We proved that TMs with one-way infinite tapes and two-way infinite tapes recognize the same class of languages.

Here is Assignment 1: [ps] [pdf]. I posted it on May 26th, and it is due on June 7th, before lecture. For policies on lateness and collaboration, check the main course web page.

Week 1
We talked about what kind of problems we will consider in this course and why they are relevant. We then started the Computability part by defining what a Turing Machine is and going through an example. As a motivation for Turing's work, we mentioned Hilbert's tenth problem. This corresponds to sections 3.1 and 3.3 in Sipser's book.

If you want to see a Turing Machine at work, there are various simulations on the web. Here is one, and here is another one. Each simulation might have a special way to enter the transition function and it's tape might be only one-way (as opposed to two-way) infinite. For course purposes, we'll stick with the definition from class. I'm posting these links mainly for fun.