This is a three-credit required course for the undergraduate CS
program. The course prerequisites are Discrete Math (COMS W3203) and, to a
lesser degree, Data Structures (COMS W3137), or the instructor's
permission.
The course is on Tuesdays and Thursdays. There are two sections:
Lectures for Section 001 will take place from 11:40am-12:55pm in 428 Pupin Laboratories.
Lectures for Section 002 will take place from 10:10am-11:25am in 702 Hamilton Hall.
The final exam for both sections will take place Thursday, May 7th from 10:10am - 12:55pm in 417 IAB.
Instructor and office hours
All TA office hours are in the
Computer Science TA room in Mudd.
All of Professor Malkin's office hours are in 514 CSB. If you do not have
swipe access to the computer science building, please ask someone in the
office to let you in.
Office hours by day
- Friday (5/1)
- Prof. Malkin - 10:00am-11:00am
- Rhea Goel - 12:00pm-2:00pm
- Alfred Tan - 2:00pm-4:00pm
- Sunday (5/3)
- Alfred Tan - 5:00pm-7:00pm
- Monday (5/4)
- Lucas Kowalczyk - 2:00pm-4:00pm
- Jeffrey Handler - 4:00pm-6:00pm
- Recitation (Luke Kowalczyk) - 6:30pm-8:00pm
- Tuesday (5/5)
- Daniel Miron - 10:00am-12:00pm
- Marshall Ball - 12:00pm-2:00pm
- Prof. Malkin - 2:00pm-3:00pm
- Ellen Vitercik - 3:00pm-5:00pm
- Jeffrey Handler - 5:00pm-7:00pm
- Kunal Jasty - 7:00pm-9:00pm
- Wednesday (5/6)
- Prof. Malkin - 11:00am-12:00pm
- Marshall Ball - 4:00pm-6:00pm
- Rhea Goel - 6:00pm-8:00pm
Class description and syllabus
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/20) Motivation and overview of the class. Definitions of alphabet, strings and languages. Examples and definition of DFA and language recognized by a DFA. Readings: Chapter 0, 1.1. Homework 1 posted.
-
Lecture 2 (1/22) Review of DFA and Regular languages. All finite languages are regular. More examples of (infinite) regular languages and intuition for languages that may not be regular. In one section we started discussion of NFAs. Readings: 1.1.
-
Lecture 3 (1/29)
Definition and examples of NFA, how it computes (via tokens or via a computation tree), and the language recognized by it. 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. Homework 1 due.
- Lecture 4 (2/3)
The subset construction converting any NFA to an equivalent DFA: example, discussion of the exponential blowup in the number of states (showed a language for which this blowup is inherent, though we did not prove the lower bound). Defined operations on languages: complement, union, concatenation, power, Kleene star. The class of regular languages is closed under all these operations: we showed the proof for complement (using a DFA) and union (using an NFA). Readings: 1.2. Homework 2 out.
- Lecture 5 (2/5)
Showed closre of the class of regular languages under various operations (including two alternative proofs for closure under intersection and discussion of some flawed proofs). Defined the regular operations (union, concatenation, star), the syntax of regular expressions, and the language they describe. A language is regular if and only if it can be generated by a regular expression: we proved one direction (RE to NFA). Reading: 1.3
- Lecture 6 (2/10)
Showed the NFA to RE transformation (using GNFA and
ripping states). Noted complexity of transformations
from RE to NFA (linear) and NFA to RE
(exponential). Examples.
Reading: 1.3. HW 2 due. HW 3 out.
- Lecture 7 (2/12)
Proved that every regular language satisfies the
pumping lemma, and discussed how to use this (in the
contrapositive form) to prove that a language is not
regular (including examples). Noted that this is not a
characterization (some languages satisfy the pumping
lemma but are not regular), so this method does not
always work. Gave an example of using closure
properties of regular languages to prove that a
language is not regular. Reading: 1.4.
- Lecture 8 (2/17)
Wrapped up discussion on regular languages and
proving non-regularity (including review of
complexity of transformations among DFA/NFA/RE, in
particular linearity of RE to NFA transformation, and
another example of using pumping lemma). Defined
context-free grammars and the languages they generate,
and gave some examples. Reading: 2.1. HW 3 due.
- Lecture 9 (2/19)
Defined parse trees and left-most derivations, and
claimed their one-to-one correspondence. Defined
ambiguous grammars and gave examples. Defined
ineherently ambiugous languages, and gave an example
without proof. Showed an example of a CFG with a
detailed proof of correctness (proving that it
generates a given language). Reading: 2.1. HW 4 out.
- Lecture 10 (2/24)
Defined regular grammars (CFG where each rule is of
the form A → aB or A → a or A →
ε. Stated (without proof) that a language is
regular if and only if it has a regular
grammar. Concluded that every regular language is
context free.
Defined Chomsky normal form (CNF) for CFG. Stated
(without proof) that every CFG can be generated by one
in CNF. Introduced PDA (pushdown automata) and showed
examples. A language is context free if and only if it can be
recognized by a PDA (we showed the CFG to PDA
transformation, did not show the other direction).
Concluded (again) that every regular language is
context free (as NFA to PDA transformation is trivial).
Reading: 2.2
- Lecture 11 (2/26)
Tandem pumping lemma (pumping lemma for context free
languages): statement, proof, and examples of how it
can be used to prove that a language is not context
free. Reading: 2.3. HW 4 due (practice HW5 out).
- Midterm (in class): (3/3)
- Lecture 12 (3/5):
Introduction to general computability and Turing
Machines (TM). TM definitions: machine,
configurations, language of a TM, TM-recognizable and
TM-decidable languages. Mentioned some variants of
TMs: a TM that can move right, left, or stay put (we
showed equivalence), and a machine with
doubly-infinite tape (we claimed equivalence but
didn't show it).
Reading: 3.1.
- Lecture 13 (3/10):
Complete examples (with state diagrams) of TM
computation. Defined input-output TM and computable
functions, and gave examples. Discussed variants of
TM and defined multi-tape TM.
Reading: 3.1, Definition 5.7. Midterms returned.
- Lecture 14 (3/12):
Proved equivalence of multi-tape TM and standard (one
tape) TM. Mentioned (without detail or proof) that
this simulation incurs a quadartic overhead in
runtime, and this is unavoidable in general. Defined
non-deterministic TM (NTM), and proved their
equivalence to standard (deterministic) TM. This
transformation involved performning a breadth-first
search of the computation tree of the NTM. Mentioned
(without detail) that this simulation incurs an
exponential overhead in runtime, and whether or not a
more efficient simulation exists is one of the biggest
open problems in computer science (we will talk about
this later in the class). Church-Turing thesis, and
our shift to high-level algorithm/TM description.
Reading: 3.2, 3.3. HW6 out.
- Lecture 15 (3/24) taught by Marshall:
Reviewed set cardinality and definition of countable
sets. Showed the set of all strings is
countable. Defined counters and Counter Machines. Proved
TMs are equivalent to 2-Counter Machines. Defined
Enumerators and Length-Increasing Enumerators. Proved a
language is decidable if and only if it has a Length
Increasing Enumerator. Proved a language is recognizable
if and only if it has an Enumerator. Reading: 3.2,
4.2. Notes on Courseworks. Note that the material on
counter machines is not in the textbook.
- Lecture 16 (3/26) taught by Marshall:
General remarks about encodings of objects, see notes
from Tues and Thursday for details. Concluded, via
counting argument (not fully specified), that most
languages are not TM-recognizable. Gave a description of
a Universal Turing Machine and its language. Loosely
discussed the notion of decision problems and how they
correspond to languages. Showed that the languages
corresponding to the following decision problems are
TM-Decidable: Membership for DFAs, NFAs, CFGs; Emptiness
for DFAs, CFGs; Equality for DFAs. Reading: Sipser
4.1. Notes on Courseworks. HW6 due.
- Lecture 17 (3/31):
Brief review of TM material (TM-recognizable vs
TM-decidable, many equivalent models, CT thesis
("TM=algorithm"), dovetailing technique).
Proved that L is decidable if and only if both L and
its complement are recognizable (Corollary: if L is
undecidable, either L or complement(L) is not
recognizable).
Brief overview of what is coming up: we'll prove that
there exist many languages that are not
TM-recognizable. Then we'll show one specific
(arguably contrived) language that is not
TM-decidable. Then we'll show several natural and
important languages that are not decidable. Finally,
we'll show that any non-trivial language-property is not
decidable (we'll clarify what this means later, but
this is a huge class of problems we would have liked
to solve but are not solvable). Key point towards
proving all this is the fact that any TM (or
program/algorithm) can be encoded as a string (or a
number), and given as input to another TM that can
read it, manipulate it, and/or simulate it.
Reviewed the definition of a countable set (mentioned
examples: integers, even integers, rationals, strings
over any alphabet, binary strings, TMs).
Theorem: the set of all languages over an alphabet
Sigma (e.g., binary) is uncountable. Proof via
diagonalization (same technique can show
uncountability of reals, infinite strings, subsets of
a countable set). Corollary (since there are
countably many TMs
and unountably many language): there are (uncountably
many) languages that are not TM-recognizable.
We then defined X_TM and proved that it is not
decidable ("paradox" proof). Reading: 4.2.
HW7 out.
- Lecture 18 (4/2):
X_TM is not recognizable (proof from last lecture can
be extended to show this, but we showed an equivalent
proof via diagonalization). Proved that A_TM is
recognizable (by the universal TM) but not decidable
(if it was, then X_TM would be as well). Thus,
complement(A_TM) is not recognizable.
Proved that H_TM ("the halting problem") is
reognizable, but not decidable (if it was, A_TM would
be as well). Proved that E_TM is not decidable (if it
was, A_TM would be as well). Briefly discussed the
general reduction proof technique and what a
"Turing-reduction" is. 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.
- Lecture 19 (4/7): Defined Turing reductions
and discussed how to use them to prove decidability
and undecidability. 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 undecideable then B is
undecidable. Recast results from last lecture in terms
of Turing reducibility, and proved that EQ_TM and REG_TM
are not decidable. Stated and proved Rice's theorem.
Reading: 5.1 (beginning), 6.3, problem 5.28 (and its
solution). HW7 due. HW8 out.
- Lecture 20 (4/9): Review of Rice's theorem
and its proof. Applying it to ALL_TM
example. Discussion of implications of undecidability
results to broad unsolvability of problems regarding
modern programs, even for simple instances. Summary of
methods we saw so far for proving undecidability or
unrecognizability of languages. Definition of mapping
reductions ("question converters"). A mapping
reduction from A to B implies a Turing reduction from
A to B; in fact, it is equivalent to having a Turing
reduction from A to B where the oracle is called
exactly once, and its answer is kept as the output.
If A is mapping reducible to B and B is recognizalbe,
then A is recognizable. Thus, if A is mapping
reducible to B and A is not recognizable, B is not
recognizable. A is mapping reducible to B if and
only if complement(A) is mapping reducible to
complement(B).
Reading: problem 5.28 and its solution. 5.3.
- Lecture 21 (4/14):
If A is Turing reducible to B via a reduction that
calls the oracle exactly once and flips its output,
then A is mapping reducible to complement(B).
Prove that EQ_TM is neither recognizable (by mapping
reduction from E_TM to EQ_TM) nor co-recognizable (by
mapping reduction from complement(A_TM) to
complement(EQ_TM)).
Showed that as a consequence of the proof of Rice's
theorem, we have the following: If P is a
non-trivial language property, and N is the TM that
rejects all inputs, then: (1) if N is in P then P is
not recognizable; (2) if N is not in P then
complement(P) is not recognizable.
Informal overview of using reductions via
computation histories to show undecidability (all the
following was done only as a high level overview,
skipping most details): Definition of an accepting
computation history. M accepts w if and only if there
exists an accepting computation history of M on
w. ALL_CFG is undecidable: sketched the proof using a
Turing reduction from A_TM, via accepting computation
histories technique. Post's correspondence problem
(PCP): described the problem, and noted that it is
undecidable, again via a reduction from A_TM with a
similar technique (no details). 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 EQ_CFG, some logical theories, and other
problems (we mentioned that there is no algorithm that
can decide in general whether a statement about number
theory is true or false, and mentioned Goedel's
incompleteness theorem).
Reading: 5.3, problem 5.28 and its solution (this is
Rice's theorem; the extension of it that we mentioned
in class is not in the text). We superficially touched
upon some of the material in the second half of 5.1,
5.2, and 6.2. HW8 due. HW9 out.
- Lecture 22 (4/16):
Introduction to complexity theory: review of big-oh
notation, defined running time of a machine, the
language classes Time(t(n)) and P (polynomial time
computable). Discussed robustness of the definition
of P to various models of computation, and its
robustness to various input representation (e.g.,
binary vs decimal, but not unary). Discussed the
strong Church-Turing thesis (and its relation to,
e.g., quantum computing). Examples of languages in P:
detecting simple cycle in a graph (and other examples
without proof). Reading: 7.1, 7.2.
- Lecture 23 (4/21): Review of P and some
examples (without proof). Defined the class EXPTIME.
Defined the class NP (polynomial time verifiable).
Examples: COMPOSITES is in NP (via grade-school
algorithm) -- mentioned that it is also in P (via more
sophisticated algorithm which we didn't show).
HAM_CYCLE is in NP (mentioned that it is not known to
be in P - figuring that out would solve the P vs NP
question). P is a subset of NP which is a subset of
EXPTIME (sketched the proofs, which are easy). P is
known not to be equal EXPTIME, but we do not know
where NP falls (could be equal P, equal EXPTIME, or
somewhere in between). Discussed the importance and
intuitive meaning of P vs NP problem. If L is in P
then complement(L) is also in P. We do not know
whether the analogous theorem for NP is true (suspect
that it is not). Reading: 7.3 (beginning).
HW9 due.
- Lecture 24 (4/23): Review of P (easy to
compute) and NP (easy to verify), the P vs NP problem
(sometimes thought of as "can creativity be
automated?" and its potential implications in every
area of our life.
Definition of runing time for a non-deterministic TM
(NTM). Proved an alternative characterization of NP
via poly time NTM. We can simulate any NTM on a
(deterministic) TM in exponential time (another proof
that NP is a subset of EXP), but we do not know
whether we can do so in poly time (if we could,
P=NP). Discussed why this is not contradicting the
strong Church-Turing thesis, as NTM is not a
reasonable model of computation.
Defined poly time reduction (poly time equivalent of
mapping reduction). Defined NP-hard languages, and
NP-complete languages (a language that is in NP and is
NP-hard). If A is poly reducible to B and B is in P,
then A is also in P.
If A is poly reducible to B and B is poly reducible to
C, then A is poly reducible to C.
If A is poly reducible to B and A
is NP-hard, then B is also NP hard.
Defined CNF-SAT and 3SAT, and sketched a polytime
reduction from CNF-SAT to 3SAT. Noted that CNF-SAT is
NP-hard, and thus 3SAT is too.
Reading: 7.3, 7.4 (first two parts).
HW10 out.
- Lecture 25 (4/28):
Review of NP, reduction, and NP-completeness.
Definition of coNP. We believe that NP is different
from coNP (P is contained in the intersection),
but it is also possible that P=NP=coNP.
If A is poly reducibe to B, A is NP complete, and B is
in NP, then B is also NP complete.
If L is NP complete, then L is in P if and only if
P=NP.
Reviewed (in a bit more detail) the definitions of a
Boolean formula and when it is satisfiable, and
defined the languages SAT, CNFSAT, and 3SAT.
Provided a proof sketch for the claim that SAT is
poly reducible to CNFSAT, which is poly reducible to
3SAT.
Stated Cook-Levin theorem: SAT is NP complete.
Corollary: CNFSAT and 3SAT are also NP complete.
Defined Independent_Set and proved that it is NP
complete (by reduction from 3SAT).
Reading: 7.4 and 7.5 (although we did different
examples at times).
- Lecture 26 (4/30): Cook Levin theorem:
proof sketch. Some other examples of NP complete
languages. Decision problems (languages / yes/no
questions) vs search problems (finding a solution /
more than one bit output): Showed that the search
problem for SAT (find a satisfying assignment) would
be solvable in poly time given an oracle solving the
decision problem (does there exist a satisfying
assignment). In section 2 also sketched the same for
vertex cover (find a vc of size k given a an oracle
for the decision version of vc). On the other hand,
for composites/factorization, the search problem
(given N, find a non-trivial factor) is believed to be
hard (not in poly time), and this is the basis of much
of the cryptography you use every day. However, the
decision problem (given N, does there exist a
non-trivial factor) is easy (it is known to be in P).
So this is an example where search (probably) can't be
efficiently solved using an oracle for the natural
corresponding decision problem. But now consider a
different version of the decsion problem for
factoring: given N, a,b, does there exist a non
trivial factor between a and b. Any oracle solving
this can be used (using a binary search technique) to
efficiently solve the search problem and find a
factor. In general, every search problem (or
functional problem) can be solved using an oracle
solving some corresponding decision problem (given the
problem instance and i, does the i-th bit of the
solution=1). So in this sense it is sufficient to
focus (as we have been througout the class) on
languages (decision or yes/no problems). We very
briefly mentioned optimization problems and the concept
of approximation algorithms. Discussed what are the "next
classes" that continue this one (most notably
complexity and algorithms) Reading: 7.4, 7.5 (decision
vs search seems not to be in the text). HW10 due 5/1.
Recitations will typically be held Fridays from 3:00pm-4:30pm in 312 Math. Handouts with problems covered in recitation are posted on
courseworks.
-
Recitation 1 (1/30) - Rhea Goel
-
Recitation 2 (2/6) - Marshall Ball
-
Recitation 3 (2/13) - Alfred Tan
-
Recitation 4 (2/20) - Daniel Miron
-
Recitation 5 (3/1) - Jeffrey Handler - Note this is a Sunday, not Friday like usual. Time: Sunday 3:00-4:30pm, Math 417.
-
Recitation 6 (4/2) - Kunal Jasty - Note this is a Thursday, not Friday like usual. Time: Thursday 8:30-10:00pm, 233 Mudd.
-
Recitation 7 (4/12) - Ellen Vitercik - Note this
is a Sunday, not Friday like usual. Time: Sunday
2:00-3:30pm, 233 Mudd.
-
Recitation 8 (4/19) - Ellen Vitercik - Note
this is a Sunday, not Friday like usual.
Time: Sunday 3:30-5:00pm, 312 Math
-
Recitation 9 (4/24) - Rhea Goel
-
Recitation 10 (5/4) - Luke Kowalczyk - Note
this is a Monday, not Friday like usual.
Time: Monday 6:30-8:00pm, 428 Pupin
Each homework is due 10 minutes before the start of each class. You must bring a hard copy to class, and also turn in an electronic copy on Courseworks. Homeworks must be typed or legibly written and scanned for the electronic copy. LaTeX is preferred. The electronic submission should be a single pdf file named after your UNI: [UNI].pdf
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.
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, PWS Publishing Company. 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
Related courses and links
CS 3261 constitutes the last CS Theory course required to be taken by
all CS majors. Students interested in the material covered by this course
are strongly encouraged to pursue some of the advanced courses offered in
in theoretical computer science. See
the theory group's webpage
for more information and a list of past and current theory courses. 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 W4252: Introduction to Computational Learning Theory.
- COMS
W4261: Introduction to Cryptography
- COMS W4995: Introduction to Communication Complexity
- Several different classes related to graph theory: COMS
W3203, COMS W4203, CSOR E4010.
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.
-
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).
-
Finite State Automation Applet is an automaton simulator, similar
to JFLAP. Requires Java.
- 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 , with a
Belarusian
translation here.
- P vs. NP Video introducing complexity classes P and NP.