University of Toronto,
Department of Computer Science
CSC463H Computational Complexity and Computability
Winter 2012
Students should consult this page at least once a week and check for new announcements.
Course Info
 Instructor
 Name: Kaveh Ghasemloo
 Email:
 Office: 10 King's College Road, Sandford Flemming Bulding, Room 4306B
 Teaching Assistants:
 Names: Yu Wu & Dustin Wehr
 Email:
 Lectures
 When: Wednesdays 6PM8PM
 Where: BA 1210
 Tutorials
 When: Wednesdays 8PM9PM
 Where: BA 1210
 Office Hours
 When: Wednesdays 5PM6PM
 Where: SF 4306B
 or email the instructor for an appointment.
 Course Website
 http://www.cs.toronto.edu/~kaveh/csc463h/
 http://j.mp/csc463h
 Textbook
 Michael Sipser, "Introduction to the Theory of Computation", 2nd Edition, 2006.
 Supplementary Lecture Notes (by Stephen Cook)
 Turing Machines and Reductions
 Computability and Noncomputability
 NP and NPCompleteness
 References
 S. Arora and B. Barak, "Complexity Theory, A Modern Approach", 2009.
 Free online draft.
 Oded Goldreich, "Computational Complexity: A Conceptual Perspective", 2008.
 Free online draft.
 Michael R. Garey and David S. Johnson, "Computers and Intractability: A Guide to the Theory of NPCompleteness", 1979.
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction to Algorithms", 3rd Ed., 2009.
 Dingzhu Du, KerI. Ko, "Problem solving in automata, languages, and complexity", 2001.
 Course Material
 Course Description
 Course Contents
 Marking Scheme

Marking Scheme Title Points Notes Assignments 55 A0: 5 pints, A1: 10 points, A2: 15 points; A3: 10 points, A4: 15 points.
Tests 20 T1: 10 points; T2: 10 points.
Take Home 10 See the instructions below.
Final Exam 40 To pass this course you should get at least 50% in the final exam.
Total 125 Anyone with score above 100 points will get 100 points (the extra points are bonus, i.e. if you miss a test and an assignment worth 15 point you still can get 100 points).
 Course Information Sheet
 csc463w12info.pdf
General Remarks
 Email is the preferred way to contact the instructor and the teaching assistant. Feel free to email the instructor regarding any course related issues. Questions by email are also welcome. We will try to answer your emails in 3 working days.
 Please use informative subject lines for your emails and include "[CSC463]", e.g. "[CSC463] a question about Turing machines" or "[CSC463] clarification for assignment 1".
Announcements
 May 1, 2012
 Marks are submitted. They should appear on ROSI soon. Average mark: 74%.
 Questions 3 and 8 in the fianl exam were more difficult than I intended and only a few students could answer them so I relaxed the 50% score requirement for passing the course.
 Apr. 18, 2012
 The course finished today. I hope that you have enjoyed it. Have a great summer. :)
 Apr. 16, 2012:
 If you have questions you can drop by BA3201 on Tuesday, Apr. 17, from 4PM to 6PM to ask them.
 I will post some marker remarks today about assignments and tests. Please check the site tonight if you want to read them.
 Apr. 13, 2012:
 The Help Center (located in BA2270) is open during the exam period from MondayThursday 46pm. You can drop by the Help Centre to ask questions.
 You can also ask questions on the following CS Q&A website: Computer Science  Stack Exchange. If you have trouble finding reductions between NPcomplete problems, check this post by Jeff Erickson.
 Email questions are welcome as always. If you have a question, don't leave it to the last day. You can also ask for your scores in the tests and assignments. I strongly recommend that you pick up your test and assignment papers so you will not repeat them in the final exam. You can drop by the help center to pick them up from Dustin (TA) during the its operation hours.
 Take Home papers will not be marked before the final exam.
 Apr. 12, 2012:
 Test T2 is marked. Email the instructor if you want to know your mark. You can pick your test papers tomorrow afternoon, from 2PM4PM from my office.
 Assignment A4 is being marked but not finished yet. You can pick up your assignment A4 papers tomorrow as well. Also assignment A3 papers if you haven't picked them up.
 Regarding the Final Exam
 The final exam will be about the whole course (both computability and complexity). There will be no definition questions, but if you don't know the definitions you will have hard time solving the problems. The exam will be 3 hours long. .
 To prepare for the final exam: check the previous semester's final exam for sample questions. Make sure that you know the definitions (as stated in the book), and the solutions to the assignments and tests. Study examples and problems in the textbook from the chapters we have covered from the textbook (ch. 3,4,5, 7, 8, 9.1) (particularly reductions and completeness proofs). You can study the previous semester's assignments/tests.
 Reminder: to pass this course you must get at least 50% in the final exam. If you don't, you will fail the course independent of how well you have done in the assignments/tests.
 The proofs of the following theorems will not be in the final exam: CookLevin theorem (SAT is NPcomplete), Path is NLcomplete, NL=coNL.
 CFGs/CFLs will not be part of the final exam.
 No aids are allowed in the exam. For more information about what you can or can't bring to the exam check the regulations for final exams. If in doubt or have questions please talk to the undergrad office.
 Apr. 8, 2012:
 The solutions for assignment A4 are posted.
 Apr. 5, 2012:
 For assignment A4, question 1, if you have trouble solving the problem solve it with using integers in place of just 0 and 1 in vector b. Note that a >= t iff there is a nonnegative integer w s.t. a+w = t.
 I will have an office hour on April 17, from 4PM to 6PM.
 One of the TAs will have an office hour on April 16. I will post the time after I check it with TAs.
 You can pick up your assignment A3 this afternoon (2PM3PM).
 Mar. 31, 2012:
 I will hold an office hour on Monday, April 2, from 4PM to 5PM.
 If you are struggling to finish the assignment A4/takehome by the due date (Wednesday, April 4), email me and I will consider giving you up to 3 days of extension.
 Mar. 28, 2012
 Similar to the previous test, there is going to be a question about basic definitions in complexity theory that we have covered so far in the course so make sure you know these definitions from chapter 7 of Sipser.
 Mar. 27, 2012
 To prepare for the test, you may want to review chapter 7 from Sipser (particularly the NPcompleteness proofs) and the excises at the end of the chapter.
 There is an office hour tomorrow from 5PM6PM, drop by my office if you have any questions.
 Questions by email are also welcome and I will try to answer email questions quickly (till tomorrow noon).
 Mar. 26, 2012:
 Assignment A4 is posted.
 Solutions for assignment A3 are posted.
 Mar. 25, 2012:
 The due date for assignment A3 is extended till 6PM Monday, Mar. 26.
 The definition of Graph Homomorphism in the assignment is also corrected. If you have solved the question with the previous definition, that is also fine. I have also added an explanation about the extension problem.
 We will have the test T2 on Wednesday, Mar. 28, from 6PM7PM. The test will be only from the complexity theory part of the course we have covered. The space complexity will not be in the test.
 Assignment A4 will be posted tonight. The due date for it is Apr. 4, 6PM.
 I have added a list of topics selected so far, see below.
 Mar. 23, 2012:
 There will be an office hour from 4:30PM5:30PM.
 Mar. 15, 2012:
 Assignment A3 and takehome are posted. Assignment A4 will be posted also today. The dues dates are also updated.
 Please check the the first question of the takehome and let the instructor know your selected topic as soon as possible. Contact the instructor if you have difficulty selecting a topic.
 Mar. 3, 2012:
 You can drop by Yu Wu's office (SF 4302C) this afternoon to pick up your assignments.
 Feb. 28, 2012:
 We will continue the course as planned. Tomorrow we will have the first test (from 6PM to 7PM).
 The questions in the test will be similar to those you have solved in the assignments, but if you want to see more examples check the midterm tests and their solutions on the following pages:
 Remember that this test will cover only the computability part of the course.
 The solutions of the last two assignments are now accessible from the course webpage.
 For a fast review of the material you can also check François Pitt's lecture notes for CSC363H.
 I will have an office hour tomorrow from 4PM to 5:45PM before the test so if you have any questions drop by my office.
 The assignments A1 and A2 are marked, but some of them need to be remarked. You can pick them up by this Friday.
 Feb. 16, 2012:
 We have finished marking the assignments A1. We hope to finish marking assignment A2 during the weekend. Check the website during the next few days for the instructions on how to pick up your assignments.
 Next week (Feb. 20Feb. 24) is the Reading Week, so no lecture/tutorial on Feb. 22.
 Test1 will be on Wednesday, Feb. 29, 6PM7PM. The question will be from the first part of the course (computability theory, chapters: 3, 4, 5). The lecture will follow the test (7PM9PM). No tutorial on Feb. 29.
 Feb. 15, 2012:
 We have finished the first part of the course (computability theory) last week. We have started the complexity theory part this week. The plan is to cover the following chapters from the textbook: 7 (time), 8 (space), 9 (intractability).
 The due date for assignment A3 is extended to Wednesday, Mar. 7, 6PM . It is going to be mainly complexity theory questions.
 There will be an office hour on Monday, Feb. 27, 4PM6PM, two days before the test. I will announce the place of the office hour later.
 Feb. 6, 2012:
 There was a problem with assignment A2 not being linked till Saturday. I have simplified the assignment. The due date is also extended till Friday, Feb. 10, 6PM. Considering the simplification and the extension, I think that you should have sufficient time to finish it. Question 2 is also clarified.
 If you want to see more questions in addition to those discussed in the tutorial, you can check the exercises in Sipser (our textbook). It has good exercises, many of them with answers. Another good book with lots of excises is Du and Ko (see the references section)
 Jan. 30, 2012:
 The assignment A2 will be posted by tomorrow.
 The deadline for assignment A1 is now extended to Friday, Feb. 3, 6PM.
 The solutions for assignment A0 are now posed. Use "csc463h" and "winter12" to access them.
 Jan. 25, 2012:
 Since we didn't have enough time today to discuss SDhardness and SDcompleteness more carefully, I am thinking about extending the deadline for assignment A1 from Wednesday, Feb. 1, 6PM to Friday, Feb. 3, 6PM. Please let me know by Monday, Jan. 30 if you have any reservations about this.
 There will be an extra office hour next week on Monday, Jan. 30, 5PM6PM.
 The questions and solutions of problems discussed in the tutorials are available from Prof. Cook's CSC463H1 Fall 2011 course webpage.
 The Complete version of assignment A1 is posted.
 Assignment A0 is updated to clarify that machine model is onesided and that your machines only needs to work on inputs of correct format, you don't need to perform syntax checking.
 Added the due dates for future assignments.
 Added the dates for tests.
 Jan. 24, 2012:
 Assignment A0 is updated to clarify the definition of the successor function.
 Note that the definition of the TM given in the question 1 (including the table for the transition function) is just an example to explain the format of the answer. You should define your own TM.
 Please send the clarification questions about the assignments to the instructor.
 Jan. 23, 2012:
 You should be able to access LaTeX and Kile on CDF machines. You can find some useful links in the LaTeX resources section.
 Assignment A1 is posted. Due date is Wednesday, Feb. 1, 6PM. Questions 4 and 5 will be added after this week's lecture.
 Assignment A0 is posted. Due date is Friday, Jan. 27, 6PM.
 Jan. 18, 2012:
 You can find two TM simulators at the links sections.
 Jan. 11, 2012:
 Today's tutorial will be an introductory session to the course. I will also explain logistics (marking scheme, etc.).
 Jan. 2, 2012:
 Course starts on Jan. 11.
 Nov. 22, 2011:
 Students should check this page regularly (at least once a week) for new announcements.
Assignments (55 points)
Assignments should be written using the provided LaTeX file and the pdf version should be emailed to the email address of teaching assistant containing the appropriate subject line, e.g. ”[CSC463] Assignment 0”. You should include your full name in the email and attach your solutions as a pdf file to it. The teaching assistants will go over the solutions in the tutorial, so no late assignments will be accepted. You should not change the LaTeX template files provided for writting assignments other than filling in the parts marked as TODO. In particular, you should not change the formatting. The answer for each question should not be more than 3 pages.
 Assignment 0 (5 points)
 Due: Friday, Jan. 27, 6PM
 Questions: A0.pdf
 LaTeX file: A0temp.tex
 Solutions: A0sol.pdf
 Marker's Remarks: A0mr.pdf
 Assignment 1 (10 points)
 Due: Wednesday, Feb. 1, 6PM; Extended: Friday, Feb. 3, 6PM
 Questions: A1.pdf
 LaTeX file: A1temp.tex
 Solutions: A1sol.pdf
 Marker's Remarks: A1mr.pdf
 Assignment 2 (15 points)
 Due: Wednesday, Feb. 8, 6PM; Extended: Friday, Feb. 10, 6PM; Extended: Sunday, Feb. 12, 6PM
 Questions: A2.pdf
 LaTeX file: A2temp.tex
 Solutions: A2sol.pdf
 Marker's Remarks: A2mr.pdf
 Assignment 3 (10 points)
 Due: Sunday, Feb. 19, 6PM; Extended: Sunday, Mar. 25, 6PM; Extended: Monday, Mar. 26, 6PM
 Questions: A3.pdf
 LaTeX file: A3temp.tex
 Solutions: A3sol.pdf
 Marker's Remarks: A3mr.pdf, and some counterexamples to common incorrect solutions
 Assignment 4 (15 points)
 Due: Wednesday, Mar. 21, 6PM; Extended: Wednesday, Apr. 4, 6PM
 Questions: A4.pdf
 LaTeX file: A4temp.tex
 Solutions: A4sol.pdf
 Marker's Remarks: TBA
Tests (30 points)
 Test 1 (10 points)
 When: Wednesday, Feb. 29, 6PM7PM
 Questions: T1.pdf
 Solutions: T1sol.pdf
 Marker's Remarks: TBA
 Test 2 (10 points)
 When: Wednesday, Mar. 28, 6PM7PM
 Questions: T2.pdf
 Solutions: T2sol.pdf
 Marker's Remarks: TBA
 Take Home (10 points)
 Due: Wednesday, Apr. 4, 6PM
 Questions: TH.pdf
 LaTeX file: THtemp.tex for Q2 and Q3, THessay.tex for Q1

Takehome Topics Topic Book Selected by Cryptography Arora and Barak 3 * Quantum Computation Arora and Barak 3 Randomized Algorithms Arora and Barak 3 Average Case Complexity: Levin’s Theory Arora and Barak 1 Decision trees Arora and Barak 1 Communication complexity Arora and Barak 1 PCP theorem and hardness of approximation Arora and Barak 1 Interactive proofs Arora and Barak 0 Boolean circuits Arora and Barak 0 Computational Difficulty One Way Functions Goldreich 3 Encryption Schemes Goldreich 3 Approximation, Search or Optimization Goldreich 3 ZeroKnowledge Proof Systems Goldreich 3 *
Final Examination (40 points)
 Final Examination (40 points)
 When: Wednesday, Apr. 18, 7PM10PM
 Where: BN2N (320 Huron Street, Benson Building, 2nd Floor, Large Gymnasium, North End)
 Questions: FE.pdf
 Notes:
 Faculty of Arts and Sciences April 2012 Examination Schedule
 Faculty of Arts and Sciences Examination Reminders
 Faculty of Arts and Sciences Examination Rules
Lecture Notes
Time Table
Links
 DCS Resources
 Discussion/Bulletin Board for CSC463H
Note: although the instructor or the teaching assistant might check the board from time to time, in general it is not monitored, if you want to ask a question from them please email it to them or ask in person.  Undergraduate CS Course Help Centre
 Course Websites from Previous Years
 CSC463H1 Fall 2011: Computational Complexity and Computability by Stephen Cook
 CSC2401H Fall 2011: Introduction to Computational Complexity by Stephen Cook
 CSC363H1 Winter 2011: Computational Complexity and Computability by François Pitt
 CSC365H1 Winter 2011: Enriched Computational Complexity and Computability by Stephen Cook
 Turing Machine Simulators
 Turing IDE
Note: this seems to be a good TM simulator. I may add more samples in future.
Samples: sample.tm, ending_in_1.tm, add_1_to_the_right.tm, erase.tm, shift_right.tm.
 Tm
Note: another TM simulator.  LaTeX Resources
 TeXLive, a cross platform TeX/LaTeX distribution
 LEd, editor for Windows
 Kile, editor for Linux/Unix
 TeXShop, editor for Mac
 TeXMaker, cross platform editor
 TeX.SX, Q & A site for TeX/LaTeX
 A (Not So) Short Introduction to LaTeX2e
 Symbols accessible from LaTeX
 The Comprehensive TeX Archive Network
 Some Interesting Articles
 Turing Machine, Wikipedia.
 Turing Machines, The Stanford Encyclopedia of Philosophy (Spring 2011 Edition).
 Alan Turing, "On Computable Numbers, with an Application to the Entscheidungs problem", 1937.
 Stephen A. Cook, "The P versus NP Problem", 2000.
 Bill Gasarch, "The P =? NP poll", June 2002.
 Misc
 Theory Group at University of Toronto, Department of Computer Science
 Complexity Zoo
 Mathematics StackExchange, a Q & A site for mathematics
 Computer Science StackExchange, a Q & A site for Computer Science
 cstheory: TCS StackExchange, a Q & A site for TCS
 Theory Matters
 ACM SIGACT
 Some Theory Blogs
 Theory of Computing Blog Aggregator maintained by Arvind Narayanan
 Gödel’s Lost Letter and P=NP blog by Richard J. Lipton and Kenneth W. Regan
 in theory blog by Luca Trevisan
 my choices by Oded Goldreich
 Computational Complexity blog by Lance Fortnow and Bill Gasarch
 ShtetlOptimized blog by Scott Aaronson
 cstheory community blog
Policy Regarding Plagiarism and Academic Offense
University of Toronto has strict rules against plagiarism. You must not submit work belonging to others as yours. It is considered an academic offense and will be dealt with accordingly. The work you submit must be your own, if you are going to get help from any resource (books, online resources, people including other students, ...) other than the course material (textbook, course lecture notes) you should acknowledge them explicitly and give proper credit to them in your work.
For this course, you have the permission to discuss and work on assignments together with other students, but you should prepare the written solutions alone. It is fine to get help to understand, but the work you submit must represent your understanding in your words. You should be able to explain what you have submitted to the instructor orally without any previous preparation or notice during the semester. To make sure that you are writing what you have understood in your own words, don't take any notes from your discussions, wait a few hours before writing any notes related to them, and do not show your written answers to other students before due dates. Copying assignments and allowing others to copy your assignment are strictly forbidden.
For more information see Advice About Academic Offences by Jim Clarke