Prev: Data Flow languages and programming - Part I
Next: Monadic Spacing in Binomial Partite
From: Anonymous Number of People on 26 Oct 2009 23:58
19990823: General announcements. Goedel's question: if a theorem has a
proof of length at most n, can we find it in time O(n^2)? Another
question on what can be computed in limited time and space. Overview
of related topics from courses on algorithms, theory of computation,
formal logic. Definition of composite. Definition of prime. Examples.
The primality problem. Some representations of integers: decimal;
binary; unary; factored. The importance of specifying the input
representation. Simple algorithm for the primality problem. Time for
dividing n-digit numbers. Overall time for simple algorithm.

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.
 | 
Pages: 1
Prev: Data Flow languages and programming - Part I
Next: Monadic Spacing in Binomial Partite