COMS W3261: Computer Science Theory, Spring 2017

This course is an introduction to models of computation, computability, and complexity. We will ask questions like: How do we define the abstract notion of "computation" or a "computer"? What problems can be computed? What problems can be computed efficiently? Can we prove that some problems can never be computed, no matter how fast our computers become? The course is highly mathematical and abstract; in particular, there will be minimal programming assignments (if any) and homework problems will frequently involve proving or disproving various assertions. Students are expected to be comfortable with the material covered in Discrete Math (W3203) or the equivalent.

Topics (not exhaustive): automata and the languages they define, context-free grammars and the languages they define, Turing machines, basic complexity theory (such as P vs. NP).

We will be using Piazza to manage our class discussion board. The class page can be found here.

• Lecture 1 (1/17) Motivation and overview of the class. Definitions of alphabet, strings, and languages. Examples and definition of DFA and the language recognized by a DFA. Readings: Chapter 0 (also includes some background from discrete math), Chapter 1.1 (first subsection).
• Lecture 2 (1/19) DFAs and the languages recognized by them, regular languages. All finite languages are regular. Examples of infinite regular languages and intuition for languages that may not be regular. HW0 out (not for submission). Readings: 1.1
• Lecture 3 (1/24) Definition and Examples of NFAs, how it computes (via tokens or a computation tree), and the language recognized by an NFA. Every NFA has an equivalent DFA (subset construction), and thus a language is regular if and only if it is recognized by an NFA. Readings: 1.2. See also pages 7-9 in the HW0 Solutions, which includes the example we saw at the end of class. HW0 (not) due. HW1 out.
• Lecture 4 (1/26) Completed the formal specification of the subset construction, and discussed intuition. We proved that for the language of binary strings with n-th to last bit being 1, there's a n+1 state NFA, but any DFA recognizing this language must have at least 2^n states. We concluded that any generic compiler from NFA to DFA must have an exponential blow-up in the number of states since for some languages (though not all) the best DFA is exponentially larger than the best NFA. We then defined operations on languages (complement, union, intersection, concatenation, power, Kleene star) and said that the class of regular languages is closed under all these operations, although we only proved closure under complement so far. Reading: 1.1,1.2, as well as the following handout.
• Lecture 5 (1/31) We gave two different proofs that the class of regular languages is closed under the union operation (building an NFA and a DFA), and two proofs that it is closed under intersection (building a DFA, and using De Morgan law). We also proved that the class of regular languages is closed under concatenation and under the star operation (by building an NFA). Defined the regular operations (union, concatenation, star) and gave an overview of what we will see next time (regular expression and their equivalence to DFA and NFA). Reading: 1.1 starting with Theorem 1.25, 1.2. Optional (not covered in class): Notes on the Myhill-Nerode Theorem. HW1 due, HW2 out.
• Lecture 6 (2/2) Defined regular expressions, proved that a language is generated by a regular expression if and only if it is regular (getting a NFA from regular expression was mostly proved last time, the other direction involved a transformation from NFA to regular expressions, using GNFAs and ripping states). Noted that the transformation from regular expression to NFA results in an NFA with a number of states linear in the length of the RE (this can be proved based on our constructions, though we did not go through the proof). However the ransformation from NFA to RE can give a RE of exponential length compared to NFA size (noted without proof). Examples and discussion. Reading: 1.3
• Lecture 7 (2/7) Proved that every regular language satisfies the pumping lemma, and showed how to use it to prove a language is not regular (proving that a language L does not satisfy the pumping lemma implies that L is not regular). We saw several examples. Noted that the pumping lemma is not a characterization (some non-regular language also satisfy it) so it doesn't always work to prove a language not regular (but it works often enough to be very useful). Reading: 1.4. HW2 due, HW3 out
• 2/9: Snow day, class was canceled. Please read the following short handout, wrapping up our topic of how to prove a language is not regular.
• Lecture 8 (2/14) Wrapped up discussion on regular languages, their applications, and how to prove a language is not regular. Defined context-free grammars and the languages they generate, with examples. Defined parse trees, leftmost derivations, and rightmost derivations (each derivation corresponds to a parse tree; a parse tree can have many corresponding derivations, but only one leftmost derivation and only one rightmost derivation). Defined ambiguous grammars and gave examples. Defined inherently ambiguous languages and gave an example (without proof). Reading: 2.1. HW3 due.
• Lecture 9 (2/16) More examples of context free grammars, including an example with a detailed proof of correctness (proving that it generates a given language), and a proof that the language of valid regular expressions is context free but not regular. Defined Chomsky Normal Form (CNF), and stated (without proof) that every CFG has an equivalent one in CNF. Defined a right-linear (or regular) grammar (a CFG where each rule is of the form A → aB or A → a or A → ε. Stated that a language is regular if and only if it can be generated by a right-linear grammar (we didn't prove this but sketched the main idea). This also implies that every regular language is context free (we will see other proofs of that). Proved that the class of context free languages is closed under the regular operations (union, concatenation, star). This can also be used to prove that every regular language is context free. Mentioned that the class of context free languages is not closed under intersection or complement (we will prove later). Reading: 2.1. (part of HW4 out).
• Lecture 10 (2/21) Pushdown Automata (PDA): definition and examples. Brief informal discussion of deterministic PDAs. A language is context free if and only if it can be recognized by a PDA (we showed how to transform a CFG to a PDA, but skipped the other direction). As a corollary, every regular language is context free (since the transformation from an NFA to a PDA is trivial). Reading: 2.2. (second part of HW4 out).
• Lecture 11 (2/23) We stated and proved the tandem pumping lemma for context free languages, and showed how to use it to prove that a language is not context free (this will not be on the midterm). We noted that a finite state machine with two stacks (rather than just one that a PDA has) could recognize both non-context free languages we saw as examples (we will see later that a finite state machine with two stacks is at least as powerful as your favorite programming language). We proved that the class of context free languages is not closed under intersection, nor under complement. Wrapped up the topic of context free languages. Reading: 2.3
• Lecture 12 (2/28) Introduction to computability and Turing Machines (TM) and overview of upcoming topics. TM definitions: machine, configurations, a language recognized by a TM. Examples. Reading: 3.1. HW4 due.
• Midterm (in class)
• Lecture 13 (3/7) Review of TM, definition of a decider (capturing "an algorithm"), definition of a recongizable language and a decidable language. Detailed complete example (with state diagram) of a TM recognizing unary strings of lenght a power of 2 (which is not a CFL). Definition of an input-output TM and of a computable function. Several examples (in various level of detail) of "subroutines" that could be implemented with an input-output TM. Mentioned some equivalent variants of TM: a TM that can move right, left, or stay put, and a TM that has a doubly infinite tape (we briefly outlined how the equivalence can be proven in both these cases). Reading: 3.1, 3.3 (and definition 5.17).
• Lecture 14 (3/9) Defined a multi-tape TM, and proved equivalence to a standard TM. Noted that this transformation from multi-tape to single-tape TM incurs a qudartic overhead in running time, and that this overhead is known to be inherent (we didn't prove this). We then defined non-deterministic TMs, and proved its equivalence to standard TMs. The transformation from a NTM to a TM involved performing a breadth-first search of the computation tree, and incurs an exponential overhead in running time. Noted that whether or not this is inherent (namely whether there is a more efficient simulation of NTM by a deterministic TM) is related to the P vs NP problem, the biggest open problem in computer science, which we will cover later in the class. Reading: 3.2. Midterms returned. HW5 out.
• Lecture 15 (3/21) Overview of equivalent models to TM (including many that we haven't proved). Church-Turing thesis and discussion. Shifting to a high-level algorithm/TM description. Brief discussion of encodings of objects as strings. Showed that the following languages (decision problems) are decidable: Acceptance (membership) problem for DFA, NFA, Emptiness problem for DFA, Equivalence problem for DFA (didn't prove) and Acceptance problem for CFG (in the second section we didn't get to the last two examples until the following lecture). Reading: 3.3, 4.1
• Lecture 16 (3/23) Showed that any context free language is decidable (using the fact that acceptance problem for CFG is decidable). Mentioned (without proof) that the emptiness problem for CFG is also decidable, but equivalence problem for CFG is not decidable, and checking ambiguity of a CFG is not decidable (we will see methods to prove undecidablity soon). Discussed the Acceptance problem for TMs (the language A_TM), and showed that it is recognizable, by the universal TM (that takes as input a description of a TM M and a string w, and runs M on w). Discussed the importance of this idea that an algorithm can be expressed by a string and can be fed as input to another algorithm, which can then manipulate it, simulate it, try to reason about it, etc. Discussed why the universal TM is not a decider for A_TM and some intuition for why deciding A_TM may be hard (we will prove it's undecidable soon). Showed that the complement of the emptiness problem for TMs (ie, checking whether a given TM accepts any string) is recognizable (algorithm using a 'dovetailing' technique). Reading: 4.1. HW5 due. HW6 out.
• Lecture 17 (3/28) Proved that L is decidable if and only if both L and its complement are recognizable. Proved that the class of decidable languages is closed under complement, and mentioned (without proof) that it is also closed under union, intersection, concatenation, Kleene star.
  Brief overview of what is coming up: we'll prove that there exist languages that are not recognizable (in fact, most languages are not). Then we'll show a specific example language (arguably contrived) that is not decidable, and not even recognizable. Then we'll show many natural and important languages that are not decidable, or even not recognizable.
  Defined when a set is countble (when it is finite, or has the same cardinality as the naturals, namely there's a bijection from the naturals to the set). Every subset of a countable set is countable. Examples of countable sets: negative integers, even integers, rationals, the set of all strings over a given alphabet, any one language, the set of all TMs, the set of all python programs, the set of all recognizable languages, the set of all decidable languages. Next, proved that the set of all languages over a given alphabet (ie., the power set of the set of all strings) is uncountable. Proof via Cantor's diagonalisation argument (which can also be used to prove the set of real numbers, the set of infinite strings, the power set of any countable set, are all uncountable). As a corollary of the fact that there are countably many TMs (algorithmic solutions) and uncountably many languages (decision problems), we get that there are (uncountably many) languages that are not recognizable (problems that are not solvable).
  We defined the language X_TM (all encodings of a TM M such that M, when run on its own encoding as input, does not accept). We proved that X_TM is not deicidable (same proof can be used to prove that it's not recognizable), via the "barber paradox" proof (not really a paradox). Reading: 4.2 (the textbook has a slightly different presentation than ours, in particular it doesn't explicitly define X_TM, but the proof that X_TM undecidable is given implicitly as part of the proof that A_TM is not decidable).
• Lecture 18 (3/30) X_TM is not recognizable (same proof from last class works, and we also showed how the proof follows a diagonalization argumet). Used that to prove that A_TM is not decidable (but it is recognizable, as we've seen before). Concluded that the complement of A_TM is not recognizable. Proved that HALT_TM ("the halting problem") is not decidable (but yes recognizable). Discussion and some further examples. Discussed the general reduction technique we've been using to prove decidability and non-decidability, defined Turing reductions. If A is Turing-reducible to B and B is decidable, then A is decidable. If A is Turing-reducible to B and A is not decidable, then B is not decidable. Recast our previous proofs this lecture in terms of Turing reductions (we showed X_TM is Turing reducible to A_TM, and A_TM is Turing reducible to HALT_TM). Reading: 4.2, 5.1 (beginning), 6.3. See also poem-proof for undecidability of the halting problem (basically by reduction to X_TM and the paradox proof) -- see credits under links below. HW6 due.
• Lecture 19 (4/4) Review of Turing reductions and their use. Several examples of languages that are not decidable (E_TM, EQ_TM, REG_TM), proved via Turing reductions. Stated Rice's theorem and discussed its implication of undecidability of basically any non-trivial problem trying to analyze anything about the input-output behavior of a program. Reading: 5.1 (upto "computation histories"), Problem 5.28 (and its solution). HW7 out.
• Lecture 20 (4/6) Proof of Rice's theorem. Examples of problems that can be proved undecidable using Rice's theorem. Examples of problems (decidable and undecidable) to which Rice's theorem can't be applied, as they are not a property of recognizable languages (e.g., the set of all TMs that satisfy some property which depends on the actual implementation, not only on the language of the input TM). Summarized techniques we've seen so far to prove undecidability and unrecognizability, and reviewed some of the examples we've seen (in particular, X_TM, complement(A_TM), E_TM are all non-recognizable, and we've seen many examples of undecidable languages). Explained why a Turing reduction from a non-recognizable language A to L is not sufficient to prove that L is non-recongizable. But it is sufficient in the special case where the reduction calls the decider for L just once and outputs the same thing -- this special case is equivalent to a mapping reduction. Defined a mapping reduction and stated all the following (for now without proof): If A is mapping reducible to B, then A is Turing reducible to B (and if A is Turing reducible to B via a reduction that calls the oracle once and outputs the same, then A is mapping reducible to B). If A is mapping reducible to B and B is recognizable, then A is recognizable. If A is mapping reducible to B and A is non-recognizable then B is non-recognizable. Reading: Problem 5.28 and its solution (Rice's theorem), 5.3, 6.3. Note: Sipser's "informal notion of reducibility" in Chapter 5 is the same as the formal notion of Turing reducibility, which he defines in 6.3.
• Lecture 21 (4/11), given by Flora Min Jung Park: Reviewed mapping reductions and their relation to Turing reductions. Proved the two theorems from the end of last lecture. Proved that if A is mapping reducible to B then complement(A) is mapping reducible to compelement(B). Discussed how to use mapping reductions to prove unrecognizability, and other properties of mapping reductions. As an example, proved that EQ_TM is neither recognizable nor co-recognizable. We showed one direction via a mapping reduction from E_TM (basically noting that the Turing reduction from E_TM to EQ_TM that we have already seen before is actually a mapping reduction). We showed the other direction via a mapping reduction from complement(A_TM) (that is, a mapping reduction from complement(A_TM) to complement(EQ_TM), or equivalently, a mapping reduction from A_TM to EQ_TM). We revisited the proof of Rice's theorem, noting that it actually involved a mapping reduction from A_TM, thus yielding a refined version of Rice's theorem: For any non-trivial property P of recognizable languages, if the empty set satisfies P then P is non-recognizable, and if the empty set does not satisfy P then complement(P) is not recognizable. Used this refined version to conlude that CFL_TM is not recognizable. Reading: See Flora's lecture notes, as well as chapter 5.3 in the textbook.
• Lecture 22 (4/13) Wrapping up the computability portion of class, gave a high level overview (with most formal definitions and proofs omitted) of reductions using computation histories and their applications for undecidability of various probelms. Definition of an accepting computation history of M on w. M accepts w if and only if there exists an accepting computation history of M on w. ALL_CFG is undecidable: sketched the proof by reduction from A_TM, via computation history technique. EQ_CFG is undecidable (by reduction from ALL_CFG, proof left as an exercise). Post's correspondence problem (PCP): described the problem, and noted that it is undecidable, again via a reduction from A_TM with a computation history technique (no details given). The set of ambiguous CFGs is undecidable, by a reduction from PCP (no details). Many other languages in various domains can be proven undecidable by a reduction from PCP or from A_TM using the computation history technique, including Hilbert's 10th problem, and Church's result (relying on Goedel's work) that (informally) there is no algorithm deciding whether a theorem about number theory is true or false (no details given even about the precise statement of this).
  Introduction and motivation for complexity theory. Review of big-oh notation. Defined running time of a machine, the langauge class Time(t(n)), and P (polynomial time computable languages).
  Reading: Def 5.5, Theorem 5.13 (we sketched the proof), 7.1, 7.2 (beginning). We also superficially touched on the material in 5.2 and 6.2 but you're not responsible for this material. HW7 due. HW8 out.
• Lecture 23 (4/18) Discussed the class P and its robustness to the details of the computational model and input representation (for "reasonable" choices). The strong Church-Turing thesis. Example of a language in P (all graphs containing a simple cycle), and many other examples without a proof (including standard operations on numbers, some problems on graphs, sorting, regular and context free languages). Showed that the "grade-school" algorithm for testing whether a number is prime or composite runs in exponential time, but mentioned that there is a more sophisticated poly time algorithm (so these problems are in P). Emphasized that the running time is measured in terms of the length of its inputs, so for numbers (represented in binary say) the running time should be polynomial in the number of bits it takes to represent the number (which is logarithmic in the magnitude of the number). Defined NP, the class of problems for which a correct proof (aka certificate or witness) can be verified in polynomial time. Showed that the language of composite numbers is in NP (via a very simple grade-school level verification algorithm). This is harder to show for primes (it is true that the language of primes is in NP as well, in fact it is in P, but the algorithm is complex). Defined the complexity class EXPTIME (EXP) and mentioned that P is a subset of NP, which is a subset of EXP. Reading: 7.1, 7.2, 7.3.
• Lecture 24 (4/20) Review of P, NP, EXP, and proof that P is a subset of NP and NP a subset of EXP. Mentioned (without proof) that we know that P is a proper subset of EXP, but we don't know where NP fits in (could be equal P, equal NP, or in between). Showed that HAM_CYCLE is in NP, and also showed that it's in EXP. We don't know whether it is in P (the answer is yes if and only if P=NP). Discussed the P vs NP problem and its implications. Proved that P is closed under complement. Discussed why a similar proof does not work for NP -- in fact, we do not know whether or not NP is closed under complement (even assuming P not equal NP we still don't know). Defined poly time reductions. Defined NP-hard languages and NP-complete languages. If A is poly reducible to B and B is in P, then A is in P. If A is poly reducible to B and B is in NP, then A is in NP. If A is poly reducible to B and A is NP-hard, then B is NP-hard. Transitivity of poly time reductions (quick sketch of proof). If A, B are both NP complete then A is poly reducible to B and B is poly reducible to A. If L is NP-complete then L is in P if and only if P=NP. Reading: 7.3, 7.4. See also this non-technical video about the P vs NP problem. HW8 due.
• Lecture 25 (4/25) Review of NP completeness (and how it relates to P, NP, NP hardness). Defined the language SAT, showed it's in NP, and claimed (for now without proof) that it is NP complete. Defined CNF-SAT and 3SAT and showed that there's a reduction from SAT to CNF-SAT and from CNF-SAT to 3SAT (hence, since all of these are also in NP, all of these are NP complete). Defined the class NTIME(t(n)). Proved that NP is equal to the union of NTIME(n^k) for all k (namely, the class NP of polynomially verifiable languages is the same as the class of all languages that are decidable in polynomial time by a non-deterministic TM). Recalled that NTM are equivalent to (deterministic) TMs via a transofrmation with an exponential overhead in running time, and that whether or not there is a transformation with a polynomial overhead is exactly the P vs NP problem. Discussed how, even if P is not equal NP (as we believe), NTM do not violate the strong CT thesis, since arguably this is not a reasonable model of computation. Reading: 7.3, 7.4. HW9 out.
• Lecture 26 (4/27) Sketched the proof of the Cook-Levin theorem, showing that SAT is NP-complete. Discussed decision vs search vs optimization problems and some examples. Showed that if you had a way to solve SAT (answer whether or not any given formula is satisfiable), you could use it to find a satisfying assigment if one exists. More generally, we mentioned that search and optimization problems have decision versions such that if we can solve all the decision versions in polynomial time, then the search / optimization version will also be solvable in poly time. In particular, for any NP-complete problem, solving the problem (ie deciding the language) in polynomial time will allow us to find the certificate in polynomial time. Thus, the P vs NP problem is the same even if we don't focus only on decision problems (languages). However, there are problems that are not NP complete, for which the natrual search (find the certificate) or optimization version is believed to be harder than the decision version. Discussed the example of factoring -- given a number, find its factorization. This problem is believed to be hard (not in P), and much of the cryptography in use today relies on this (solving it in P would break the cryptographic scheme). However, the natural decision version -- given a number, find out if it is composite -- is in P. But other decision versions of factoring are as hard as the search version (e.g., given numbers m,k, does m have a factor less than k). While factoring is in NP and is believed to be not in P, it is also believed to be not NP-complete. One reason is that it is in NP intersect co-NP (ie both the problem and its complement are in NP) and it is believed that there are no NP complete languages that are also in co-NP. Discussed (briefly) ways people approach NP hard problems in practice: solving it for special cases, particualr input distributions, heuristics that work a lot of the time even if not always; Approximation algorithms. Wrapped up the class and discussed what are the "next classes" continuing this one (see some below). Reading: 7.4 (plus additional discussion not in the text). HW9 due 5/2.

Handouts with problems covered in practice sessions are posted on courseworks.

• (1/28) Sat 2:00pm-3:30pm in Mudd 833 - Anand Sundaram
• (2/5) Sun 1:00pm-2:30pm in Mudd 633 - Rudra Gopinath
• (2/11) Sat 2:30pm-4:00pm in Mudd 633 - Cindy Wang
• (2/19) Sun 2:30pm-4:00pm in Mudd 627 - Ethan Liu
• (2/25) Sat 2:00-4:00pm in Mudd 833 - Anand Sundaram - (Same material as 2/26 session)
• (2/26) Sun 1:00-3:00pm in Mudd 633 - Rudra Gopinath - (Same material as 2/25 session)
• (3/26) Sun 6:00-7:30pm in Mudd 227 - David Rincon-Cruz
• (4/1) Sat 2:30-4:00pm in Mudd 627 - Hidy Han
• (4/7) Fri 5:00-6:30pm in Mudd 644 - David Rincon-Cruz
• (4/16) Sun 2:00-3:30pm in Mudd 825 - Steven Shao
• (4/23) Sun 1:30-3:00pm in Mudd 627 - Jiahui Liu
• (5/3) Wed 1:30-3:30pm in Math 207 -- Luke Kowalczyk - (Same material as 5/4 session)
• (5/4) Thur 11:00am-1:00pm in Math 207 -- Frederick Kellison-Linn - (Same material as 5/3 session)

Each homework is due electronically through Courseworks. Homeworks must be typed or legibly written and scanned. LaTeX is preferred. The electronic submission should be a single pdf file named after your UNI: [UNI].pdf

• Homework 0 (not for submission, do before class Tue 1/24). Here are the solutions in pdf and in LaTeX.
• Homework 1 due Tue 1/31 by 9pm. HW1 LaTeX source.
• Homework 2 due Tue 2/7 by 9pm. HW2 LaTeX source.
• Homework 3 due Tue 2/14 by 9pm. HW3 LaTeX source.
• Homework 4 due Tue 2/28 by 9pm, NO LATE SUBMISSIONS ACCEPTED. HW4 LaTeX source.
• Homework 5 due Thur 3/23 by 9pm HW5 LaTeX source.
• Homework 6 due Thur 3/30 by 9pm HW6 LaTeX source.
• Homework 7 due Thur 4/13 by 9pm HW7 LaTeX source.
• Homework 8 due Thur 4/20 by 9pm HW8 LaTeX source.
• Homework 9 due Tue 5/2 by 11pm, NO LATE SUBMISSIONS ACCEPTED HW9 LaTeX source.

The homework constitutes 15%, Midterm constitutes 40%, and the final constitutes 45% of the final grade. The worst homework of each student will be dropped. Doing the homework is crucial for understanding and getting comfortable with the material; it is unlikely you will be able to do well on the tests without doing the homework. You are advised to start the homework early.

The midterm will be in class on Thursday March 2nd. It is a closed book exam, with two double sided "cheat sheets" allowed.

The final will take place during finals week, on Tuesday, May 9th, at 9:30am-11:30pm (for both sections).

Lateness policy

Typically, homework will be due a week from the assigned date. Late homework may be submitted up until 48 hrs after the homework is due for a penalty of 30% off the grade. In some cases the above lateness policy may be canceled, and no late homework will be accepted. You will be notified of this when the homework is given out.

Collaboration policy

All students are assumed to be aware of the computer science department academic honesty policy . Homework should constitute your own work. Collaboration in groups of two or three students is allowed, but not required. Collaboration in groups of more than three students is not allowed. If you do collaborate, you must write your own solution (without looking at anybody else's solutions), and list the names of anyone with whom you have discussed the problems. If you use a source other than the textbook in doing your assignment, explain the material from the source in your own words and acknowledge the source. In any case, you are not allowed to look at written solutions of any other student, even if you worked on solving the homework together. Collaboration without acknowledgment is considered cheating.

Readings and homeworks will be assigned from Introduction to the Theory of Computation by Michael Sipser. Either the Second or Third Edition is acceptable. Copies are currently available at the Columbia bookstore. The book's website and errata are available here. We will generally follow the book in class, but some departures are possible. Students are responsible for all material taught in class.

Optional text: Introduction to Automata Theory, Languages and Computation by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman

CS 3261 constitutes the last CS Theory course required to be taken by all CS majors. Students interested in the material covered by this coure are strongly encouraged to pursue some of the advanced courses offered in theoretical computer science. In particular, the following courses are very closely related in spirit to the topics covered in CS 3261:

• COMS W4236: Introduction to Computational Complexity
• CSOR W4231: Analysis of Algorithms
• COMS W4261: Introduction to Cryptography
• COMS W4252: Introduction to Computational Learning Theory.

In addition, the following courses (and quite a few others!) benefit from and relate to some of the topics covered by our course:

• COMS 4115: Programming Languages and Translators.
• COMS 4705: Natural Language Processing.
• EECS 4340: Computer Hardware Design, and CSEE E4823: Advanced Logic Design.

Useful links

• Java Formal Languages and Automata Package (JFLAP) is a useful Java tool that allows you to build automata, test out their functionality, and easily modify them.
• TikZ is a TeX package for programmatically creating graphics which can be used to draw automata. See an example here or here.
• GasTeX is a LaTeX plugin for easily drawing finite automata and graphs. See also JasTex, a small Java applet for visually drawing finite automata. It automatically generates GasTeX code.
• Detexify lets you search for LaTeX symbols by drawing them.
• Other useful LaTeX packages (included with the standard Texlive distribution) include amsmath, amsthm and amssymb (for typesetting equations), and xyfig (for typesetting automata and trees).
• Notes on the Myhill-Nerode Theorem written by TA Michael Tong (not required but highly recommended material).
• Turing's paper "On Computable Numbers", published 1936 (possibly more readable font for the symbols here).
• Scooping the loop snooper: A proof that the Halting problem is undecidable, in the style of Dr. Seuss, written by linguist Geoffrey Pullum to honor Alan Turing. Copied from his page .
• Who Can Name the Bigger Number?: An essay by Scott Aaronson, related to uncomputability and Turing Machines (read about the Busy Beaver problem, and more).
• youtube videos informally introducing the complexity classes P and NP and the implications of the P vs NP problem:
  • P vs. NP and the Computational Complexity Zoo: a 10 minute video
  • Beyond Computation: The P vs NP Problem: a 1 hour talk by Michael Sipser
• Surveys about P vs NP problem, significance, and progress (varying levels of technical details, perspectives, and philosophical discussions):
  • P=NP? Scott Aaronson, 2016
  • Why Philosophers Should Care About Computational Complexity by Scott Aaronson, 2013
  • Knowledge, Creativity and P vs NP (a very informal draft) Avi Wigderson, 2009
  • P, NP and Mathematics - A Computational Complexity Perspective Avi Wigderson, 2006 (appeared in proceedings of the International Congress of Mathematicians, Madrid)
  • The P versus NP Problem Stephen Cook, 2000 (written for the announcement of the Clay Millennium Prize).
  • The History and Status of the P versus NP Question Michael Sipser, 1992. The appendix includes the original letter from Kurt Gödel to John von Neumann (in German), as well as a translation.
• Interesting historical documents:
  • a letter from John Nash to the NSA in 1955 (declassified in 2012), regarding a cryptosystem that he proposed. In this letter Nash foresees fundamental aspects of modern cryptography and provable security, along the way clearly discussing polynomial time vs expolnential time and the difficulty of proving that a certain problem is in exponential time -- this is more than a decade ahead of the time these ideas (and P vs NP) came up in computational complexity. Original (hand-written but very legible), and PDF (transcribed by Rosulek).
  • a letter from Kurt Gödel to John von Neumann from 1956, essentially stating the P vs NP problem -- this is, again, more than a decade ahead of the time this question was posed in computational complexity. The original in German (as well as a translation to English) can be found in the appendix of Sipser's survey, and there's also a translation on Lipton's blog.