CPSC 421/501: Skeletal notes of what will be covered in class.

THIS PLAN IS TENTATIVE AND WILL PROBABLY BE MODIFIED

September 7-26 or so: Acceptance/Halting Problem and other paradoxes.

List paradoxes in handout. Give example of making things precise.
We typically use languages to describe any yes/no 0/1 true/false question,
a subset of strings/words over an alphabet.  
  * Introduce Sigma, Simga^*, empty string, etc.
  * Give examples of how to make "paradoxes" precise, when they lead to
	a real paradox, when they don't
  * Embark on making some of them precise.
  * Make the halting problem precise.

Live/Dead Code:
  * Explain why LiveCode (see handout) is acceptable.
  * Explain why it is unclear if it is decidable or not.
  * Given that LiveCode is not decidable (but acceptable), explain why
      DeadCode must be unacceptable.

General Counting
  * The set of strings over an alphabet is countable.
  * The set of subsets of a countable set is not countable.  Generally,
	set of subsets of a set, S, cannot be put into 1-1 correspondence
	with S.  Proof: if f:S->P(S), let T={s s.t. f(s) does not contain s}.
	Paradox!

Acceptance (L_yes)/Halting problem
  * Remark: It is easy to see there are undecidable/unacceptable languages
	via counting.  This uses another "paradox".
  * Decide versus accept.
  * Let A_C = <M,w>, M is a C program and M accepts (prints "yes" in a
	finite number of steps) to w.  
  * Note A_C can be accepted, via simulation.
  * Assume that H is a C program that always halts and decides A_C. Let
	D take input <M>, use H to decide if M accepts input <M> and performs
	the "opposite."  What happens when D is run on <D>? Paradox!
  * Assume L is acceptable but not decidable; then complement(L) is not
	acceptable

----------------------------------------------------------------

Starting September 26 or so:

Turing Machines (TM's).  Sipser defines them as a 7-tuple.  Specifically,
  (Q,Sigma,Gamma,delta,q_0,q_accept,q_reject) (and should add L,R, and
  blank symbol), with delta : Q x Gamma -> Gamma.
  Need to:
  * Write some simple programs (e.g., PALINDROME, DIVISBLE_BY_3)
  * Show that PALINDROME is linear on a 2-tape machine, but (claim that
	and explain why) it is quadratic on a 1-tape machine
  * Run any C, Java, etc. program; run any TM
  * Explain TM encoding by integers and 5-tuples (for delta)
  * Explain there exist universal TM's, universal C/Java/etc. programs
  * Explain time and space and give some bounds on our programs
    Note: time and space usually defined via k-tape Turing machines, which
    are defined like 1-tape machines, except that delta : Q x Gamma^k ->
    Q x Gamma^k x {L,R,S}^k
  * Here we can define Non-deterministic TM's: delta : Q x Gamma ->
    PowerSet( Q x Gamma x {L,R} ).  Say that a machine accepts an input
    if there is at least one legal accepting "path" or "set of configurations" 
    This definition appears in Chapter 3, although it could be delayed until
    NP-completeness.

Unsolvable Problems:
  * Review Acceptance Problem, Halting Problem, Dead Code, Counting argument
	in TM context.

---------------------------------------------------------------

Starting Late October or so:

We are basically done with our coverage of Ch 3-5, and we have already
	defined TIME and SPACE complexity.  Take up Ch 7 and P vs. NP.

  * Define P = languages acceptable in time polynomial in length of input.
  * Note that there is a class of languages solvable by guessing and verifying
	with forming a guess and verification taking polynomial time, yet
	there are exponentially many guesses.  This includes SAT, 3-SAT,
	SUBSETSUM, VERTEX COVER, 3-COLOR, etc.  Explain that these problems
	are, in a sense, equivalent and are the hardest problem in a class.
  * SUBSETSUM and 3SAT look totally different (at first).  Yet if we can
	solve SUBSETSUM time f(n), we can solve 3SAT in time order (f(n))^2.
 
  * Formally define reduction of one langauge to another; note that this is
	a stronger condition that being able to solve one problem with the
	solution to another--reduction means you convert an instance of one
	problem to an equivalent instance of another, and you cannot run 
	the solution to another repeatedly.
  * Formally define NP.
  * Cook-Levin Theorem: SAT and 3SAT are NP-Complete
  * Give a few easy NP-Completeness proofs: 4SAT, PARTITION; leave the
	harder reductions for the students and homework

--------------------------

Outline of Chapter 1,2,8 coverage:

What is a regular language?  (Defined via DFA)
What isn't a regular language? (Use pumping lemma and Myhill-Nerode)
What is a context-free language?  (Defined via CFGrammars)
What isn't a context-free language? (Use Pumping Lemma for CFL's)
What is in PSPACE? (Search through configuration spaces to show languages
	are in PSPACE.)

More details: 

DFA: (Q, Sigma, q_0, delta, F)  (F=final or accepting states)
	and delta: Q x Sigma -> Q .
Pumping Lemma for Regular Languages: If L is regular then there is a  q  
	such that if  w  is in L and  |w| > q  then  w=xyz with x y^n z in
	L for all n,  y is not empty, and |xy| < q.
Myhill Nerode: For any language L over Sigma and word  w  over Sigma let
	AcceptedContinuations(L,w) = { x  such that  wx is in L }.
	Let ACSets(L) be the number of distinct sets  AccCon(L,w) ranging
	over all w.  Then if ACSets(L) is infinite, L is not recognized by
	any DFA, and if ACSets(L) is finite then L is recognized by a DFA
	of ACSets(L) states, and that is the smallest number of states
	possible.

CFG: Terminals, non-terminals, production rules.
Pumping Lemma for CF Languages: If L is CF then there is a  q  
	such that if  w  is in L and  |w| > q  then  w=xyzuv with 
	x y^n z u^n v in L for all n,  yu is not empty.

PSPACE: Polynomial space.  Many natural problems have a configuration 
	space of size < 2^(poly(n)) with a natural way to "step" through
	all configurations in polynomial(n) space, so can apply a divide
	and conquer algorithm to see if the initial configuration is 
	connected to the goal configuration.