19990825: Improving the simple algorithm; still exponential time for many inputs. Redeeming feature: if input is not prime, algorithm provides easily verified certificate that it is not prime. Example: 317213509 certifies that 314159265358979323 is not prime. ``PRIMES is in coNP''; informal definitions of coNP and NP. Definition of exponents (orders) mod x. Example: exponent of 2 mod 7; exponent of 5 mod 7. Theorem 1: If exponent of u mod x is x-1 then x is prime. Theorem 2: If x is prime then exponent of u is x-1 for some u in {1,2,...,x-1}. Theorem 3: If x-1 is product of q's, each q prime, u^(x-1) mod x = 1, each u^((x-1)/q) mod x > 1, then x is prime. Fact: Can compute u^e mod x quickly. Example: 64003169 is prime. Structure of certificate of primality for any x. ``PRIMES is in NP''; checking certificate quickly. Proof of Theorem 1.
19990827: Proof of Theorem 3. Proof of Theorem 2, using some algebra. What about finding certificates quickly? Selfridge certificates. Theorem 1: If there is a Selfridge certificate for x then x is not prime. Theorem 2: If x is not prime then at least 75% of {1,2,...,x-1} are Selfridge certificates for x. Rabin's test for primality. Failure probability of Rabin's test. ``PRIMES is in coRP''; informal definitions of coRP and RP. ``PRIMES is in RP'' without proof.
19990830: Outline of proof of Theorem 1. Comments on running time of Rabin's test. Outline of proof of Theorem 2. The Miller-Bach test. Note that truth does not imply provability. State of the art in deterministic tests. Selfridge's test. Example where Selfridge's test fails. Adleman's test.
19990901: Example of Adleman's test for 12-digit numbers. Simpler test for 12-digit numbers. The concept of nonuniformity. The big question in parallelism. How to add quickly in parallel. ``NC.'' Summary of known speeds of parallel carrying, division, exponentiation. Picture of a Turing machine. Requirement that tapes be extended as necessary. Parameters in a Turing machine: number of tapes; alphabet; instructions; first instruction. Types of instructions: condition based on symbol of a tape, jump, halt yes, halt no, halt and print output tape, write symbol to a tape, move left, move right. Countability of the set of Turing machines modulo alphabet encoding. Church's thesis. Realism of speed of Turing machines.
19990903: Definition of k-tape deterministic Turing machine. Definition of k-tape nondeterministic Turing machine. Definition of tape configuration. Picture of tape. Empty tape configuration. Reading a tape. Writing and moving a tape. One step of a Turing machine. Example: copying a's and b's from tape 1 to tape 2. Example: sorting a's and b's from tape 1 to tape 4.
19990906: No class.
19990908: Simulations as a way to demonstrate the power of a model of computation. Encoding 2 tapes with 1 tape. Simulating 2-tape Turing machine operations with 1-tape Turing machine operations. Quadratic upper bound for 1-tape running time in terms of 2-tape running time. Quadratic lower bound for 1-tape recognition of palindromes.
19990910: Definition of the computation of a deterministic Turing machine on an input string. Possible results: never halts; accepts; rejects; output. Definition of halting in time f(n). Definition of using space f(n). Subtracting space for read-only input string. Subtracting space for write-and-forget output string. Definition of accepting a language. Definition of deciding a language. Examples.
19990913: Rephrasing simulation as relation between 1-tape time classes and 2-tape time classes. Definition of P. The polynomial-time mantra. Notes on quantum computers. Definition of nondeterministic computation. Computation trees. Example: nondeterministic machine to prove compositeness. Examples of computations. Definition of nondeterministic machines deciding languages.
19990915: Definition of NP. Correspondence between computations of M on x, paths through computation tree of M on x, strings specifying paths. Nondeterministic computation and certificates. Speed of simulating nondeterminism with determinism. Example of the obvious way to represent a tape inside a computer. Running time of the obvious way. Example of a slow way to represent a tape inside a computer. Running time of the slow way. Example of the Hennie-Stearns representation. Rules for the Hennie-Stearns representation.
19990917: General procedure to move the tape in the Hennie-Stearns representation. Pictures. Total cost of moving the tape to the right T steps. Total cost of moving the tape T steps in any left-right sequence. The Hennie-Stearns theorem: simulating many tapes efficiently with 2 tapes. Outline of the proof. Basic operations on a random-access machine. Extra operations: e.g., multiplication with linear cost.
19990920: Representing nonnegative integers on a tape. Recursive procedure to add two integers. Common representations of negative integers. Representing random-access memory on a tape. Reading and writing random-access memory. Outline of proof that polynomial-time RAM decidability is the same as P. Simple example of diagonalization: the real numbers are not countable.
19990922: A universal Turing machine. The halting language. A machine that accepts the halting language. Proof that no machine decides the halting language.
19990924: L is recursive iff L and complement of L are recursively enumerable. Explanation of the word ``enumerable.'' Simplest example of a non-recursively-enumerable language. Proof. More examples of non-recursive languages. A 7-tape time-4n^2 simulator of 2-tape machines. Proof that no 2-tape Turing machine decides the same language in o(n^2) time. Time gap for 2-tape Turing machines. Time gap for multitape Turing machines. Definition of TIME(T(n)). Chain of several different time classes. The Hartmanis-Stearns-Hennie theorem.
19990927: Definition of proper complexity functions. Pictures of various time classes. Major techniques to determine the complexity of a problem: diagonalization, giving precise complexity but only for a few problems; algorithm design, giving upper bounds on complexity; NP-completeness, giving conjectural lower bounds on complexity. Analogy between time and space. Breaking the analogy: reuse of space. Boolean values. Boolean functions.
19990929: Comments on first two homework assignments.
19991001: More comments on second homework assignment.
19991004: Simple Boolean functions: and, or, not. More complicated example: the parity of three variables. Expressing parity as a straight-line Boolean program. Expressing parity as a Boolean circuit. Expressing parity as a Boolean expression. Expressing parity as a CNF Boolean expression. Definition of straight-line Boolean program as a string. Interpretation of straight-line Boolean program as a function. Restrictions for Boolean circuits. Restrictions for Boolean expressions. Restrictions for CNF Boolean expressions. The CIRCUITVALUE problem. Fact that CIRCUITVALUE is in P. The CIRCUITSAT problem. Fact that CIRCUITSAT is in P. The SAT problem.
19991006: Example of first-order expressions: group axioms. Groups as models of group axioms. Models generally. Structure of formal proofs. Modus ponens. Examples of logical axioms. Design goals of logical axioms: prove many things; don't prove false things. Summary of deduction, generalization, soundness, completeness. Hilbert's strategy for deciding mathematical truth. Incompleteness.
19991008: Recap of logic. The language of ZFC set theory. Summary of axioms: extension, separation, pair, union, power, infinity, replacement, foundation, choice. Why comprehension is not an axiom. The Zermelo-Fraenkel thesis. The reflection principle for ZFC set theory. Comments on the difference between completeness and reflection. The theoremhood problem. Goedel's question again.
19991011: No class.
19991013: No class.
19991015: No class.
19991018: Definition of computable functions. Definition of computable partial functions. Expressing recursiveness of a language as computability of a function. Expressing recursive enumerability of a language as computability of a partial function. Example of computable function: multiplication. Basic examples of computable functions. Building more computable functions by minimalization, composition, recursion. Explanation of the word ``recursive.'' Definition of log-space reduction. Definition of poly-time reduction. Why logarithmic space implies polynomial time. Comments on other forms of reduction.
19991020: Proof that composition of (log-space) reductions is a reduction. Notation f^(-1)(L) for {x: f(x) in L}. Language reductions. Composition of language reductions. Fact that P is closed under reductions. Fact that NP is closed under reductions. Examples of reductions. P-complete languages. NP-complete languages.
19991022: No class. (UIC power outage.)
19991025: A generic P-complete language. Examples of elements of this language. A machine that decides this language in quadratic time. Reducing any language in P to this one. A generic NP-complete language. P-completeness and the LOGSPACE=P question. Generalization: the S=P question for any subset S of P closed under reductions. NP-completeness and the P=NP question. What is believed to be true about LOGSPACE=P and P=NP.
19991027: Rules satisfied by integer sequences. The RULESAT problem. RULESAT is in NP. Reduction from L to RULESAT, when L is decided by a 1000-state 1-tape nondeterministic machine in time n^3+2. NP-completeness of RULESAT. Outline of reduction from RULESAT to CIRCUITSAT. NP-completeness of CIRCUITSAT. More NP-complete problems: SAT, knapsack.
19991029: More NP-complete problems: integer programming, digraph coloring, Hamilton path in digraphs, Hamilton path prefix in digraphs, formal proof, formal proof prefix. Constructing certificates using solution to certificate prefix problem. Interpretation of NP-completeness of formal proof prefix problem as equivalence between difficulty of finding formal proofs and difficulty of finding any type of certificate. Summary of notions of complexity covered in the course: time and space; nondeterminism, randomness, parallelism, nonuniformity, approximation. Review of what diagonalization and completeness say about complexity. Common methods for dealing with NP-complete problems: try to solve them; change the problem; restrict the problem. The reachability problem. Turning any nondeterministic computation into reachability.
19991101: SPACE-optimized algorithm for reachability. Savitch's theorem: NSPACE(f(n)) inside SPACE(O(f(n)^2)) under minor assumptions. Analogy to the P=NP question. The NSPACE(O(f(n)))=SPACE(O(f(n))) question. TIME-optimized algorithm for reachability. NSPACE(f(n)) inside TIME(2^O(f(n))) under minor assumptions. NLOGSPACE inside P. NSPACE-optimized algorithm for reachability. Statement of Immerman's theorem: NSPACE(O(f(n)))=coNSPACE(O(f(n))) under minor assumptions. Analogy to the NP=coNP question.
19991103: The theorem behind Immerman's (coNPSACE-optimized) algorithm for reachability. The algorithm. Review of results of Rabin's random primality test. Lehmann's random primality test. Statement of results of Lehmann's random primality test. A random sorting algorithm: quicksort. Average time used by quicksort. The RWB digital signature verification problem. A random verification algorithm.
19991105: The rank of an integer matrix. The usual algorithm: Gaussian elimination. A faster algorithm: Gaussian elimination mod a 40-digit prime. Outline of basic probability theory. Definition of BPP. Definition of RP.
19991108: Definition of ZPP. How to combine RP and coRP machines for the same language into a single machine that never gives an incorrect answer and almost always halts quickly. Analyzing probabilities for a simple random algorithm. Picture of P, ZPP, RP, coRP, BPP, NP, coNP. What is believed to be true about randomness; possibility that BPP=P.
19991110: Building chips to decide languages. Existence of Boolean circuits that decide {x in L: x has length n}. Size of those circuits. Existence of much smaller circuits if L is in P. Time needed to precompute those circuits. Converse: L is in P if L has a quickly computable family of circuits. Definition of non-uniform polynomial time. Examples of multiplication circuits. An undecidable language decidable in non-uniform polynomial time.
19991112: Structure of a typical machine for deciding a language in RP. Example: composites. Proof that the language can be decided in non-uniform polynomial time. Explicit construction of circuits deciding the language. Probability that the sum of 6n+1 independent random variables is below 3n, if each variable is 0 with probability q, 1 with probability 1-q, for q at most 1/4. Structure of a typical machine for deciding a language in BPP. Proof that the language can be decided in non-uniform polynomial time. Picture of uniform and non-uniform complexity classes. What is believed to be true about NP and non-uniform polynomial time.
19991115: Can we prove BPP=P? Picture of a random Turing machine with human coin flips. How rand() expands a short seed into a long sequence of bits. How random() expands a short seed into a long sequence of bits. Using random() to run a random Turing machine. Problem: this drastically changes the success probabilities for many machines. Cryptographic random number generators. Example: the DES generator. Conjectural bound on DES distinguishing probability for fast machines. A slow machine with a large DES distinguishing probability. Strategy for eliminating randomness from a fast machine, assuming the DES bound.
19991117: Definition of unpredictability in time T (with probability difference 0.1). Example: uniform implies unpredictable. Example: 50% aaaaa, 50% bbbbb is unpredictable in time 1, predictable in time 3. Example: conjectured unpredictability of SPRAY. The Blum-Blum-Shub generator, from 4b bits to n bits. The Alexi-Chor-Goldreich-Schnorr theorem: predictability of BBS in time T implies factorizability of many 2b-bit numbers in time 10^20 n^2 b^3 (T + 100 nb^2). Comparison to best known factoring algorithm. Unpredictability of BBS under plausible assumption on difficulty of factoring. Typical choice of b in terms of n when T is around n^2. Yao's approach to derandomizing BPP using BBS. Time analysis. Possibility of proving BPP=P by the same approach.
19991119: What we hope is true about unpredictability. Consequence for BPP=P; expansion of time bounds. Comments on various homework assignments. Introduction to parallelism.
19991122: Parallel sums. Picture of the obvious circuit: depth n-1 using n-1 gates. Picture of a better circuit: depth lg n using n-1 gates. The obvious circuit for parallel sums. Some circuit costs: depth n-1 using n-1 gates; depth 2 lg n - 2 using 2n - lg n - 2 gates; depth lg n using (1/2) n lg n gates. Picture of the smallest-depth circuit for n=8. The same circuit for products. The same circuit for exclusive or. Generalization to any associative binary operation. Converting a typical linear recurrence into a matrix product; evaluating the matrix product in parallel. Example of integer addition: 1010111 + 1000011. The general integer addition problem given alpha_i, beta_i. Formula for answers gamma_i using carries c_i; recursion for c_i. Boolean matrices. Converting the c_i recursion into a Boolean matrix product. Time to multiply two of these matrices; consequence for depth of integer addition.
19991124: Adding k integers modulo 2^m. Cost of adding in pairs; example for 4 integers. The 3-to-2 trick. Repeating the 3-to-2 trick on many integers. Total cost of adding k integers. Example of integer multiplication. A parallel algorithm for reachability. Definition of NC_j. Examples. Definition of NC.
19991126: No class.
19991129: NSPACE(log n) contained in NC_2. Proof. NC_j is closed under reductions for j at least 2; belief that P-complete problems are not in NC. Picture of the circuit constructed in the proof. Table comparing time, space, and depth of (f(x),g(x)) and f(g(x)).
19991201: Parallelism in practice: communication costs in real circuits, communication costs in the MasPar, communication costs in PCs connected by the Internet. Approximating node cover to within a factor of 1/2.
19991203: Approximating knapsack to within a factor of 99/100. Non-approximability of the travelling salesman problem.