Complexity Theory Spring 2020


Charles E. Hughes
Computer Science
University of Central Florida


Structure: TR 1330-1445 (1:30PM-2:45PM); HEC-103; 28 class periods, each 75 minutes long.
Go To Week 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Instructor: Charles Hughes; Harris Engineering Center 247C
Office Hours: TR 10:45AM-12:00PM
GTA:  Paniz Abedin; HEC-354, Cubicle 2
Office Hours: MW 3:00PM-4:30PM (starting January 20)

Required Reading: All class notes linked from here.

Recommended Reading

Web Pages:
Base URL:
Notes URL: Introductory Notes; Formal Language and Automata Theory; Computability Theory; Complexity Theory

Assignments: Around 6 to 10; Paper + Presentation

Exams: midterm and a final.

Exam Dates (Tentative): Mid Term – Tuesday, March 3; Spring Break – March 9-14; Withdraw Deadline – Friday, March 20; Final – Tues., April 21, 1:00PM–3:50PM

Evaluation (Tentative):

  1. Mid Term – 125 points; Final Exam – 200 points (balance between weights will be adjusted in your favor)
  2. Assignments – 75 points; Paper and Presentation – 75 points
  3. Extra -- 25 points used to increase weight of best exam,  or maybe presentation, always to your benefit
  4. Total Available: 500
  5. Grading will be  A >= 90%, B+ >= 85%, B >= 80%, C+ >= 75%, C >= 70%, D >= 50%, F < 50%; minus grades might be used.


Weeks#1: (1/7, 1/9) -- Syllabus; Introduction; Formal Languages and Automata Theory
  1. Ground rules
  2. Decision problems
  3. Solving vs checking
  4. Procedures vs algorithms
  5. Introduction to theory of computation
  6. Terminology, goals and some historical perspective
  7. Review of automata (finite, pushdown, linear bounded, Turing machines)
  8. Review of formal languages (regular, context free, context sensitive, phrase structured)
  9. Review material created by Prof. Jim Rogers, Earlam College
  10. Review material from Prof. Workman, UCF

Financial Aid (Assignment#1)

Survey at Webcourses
Due: Friday, January 10 at 11:59 PM

Week#2: (1/14, 1/16) -- Formal Languages and Automata Theory
  1. Continue Automata/Formal Languages Review
  2. MyHill-Nerode as proof of min DFA uniqueness
  3. Myhill-Nerode as a tool to show languages are not regular.
  4. The chosen language is
    L = { an bm | n is not equal to m}.
    This can be shown easily in an indirect manner by showing its complement is not regular, A direct approach is using right invariant equivalence classes as it is not amenable to the Pumping Lemma.
  5. Review of reduced CFGs
  6. Chomsky Normal Form (CNF)
  7. The use of CNF in the Cocke-Kasami-Younger O(N3) parsing of CFLs generated by CNFs.


Week#3: (1/21, 1/23) -- Formal Languages and Automata Theory
  1. Pumping Lemma for CFLs
  2. Show L = { ww | w is in {a,b}+ } is not a CFL
  3. CSG for L
  4. Non-closure of CFLs under intersection and complement
  5. CFG for the complement of L
    { xy | |x| = |y| but x is not the same as y }
    can be first viewed as
    {x1 a x2 y1 b y2 | |x1|=|x2|, |y1|=|y2|} Union
      {x1 b x2 y1 a y2 | |x1|=|x2|, |y1|=|y2|}.
    But this can also be seen as
    {x1 a y1 x2 b y2 | |x1|=|x2|, |y1|=|y2|}.Union
      {x1 b y1 x2 a y2 | |x1|=|x2|, |y1|=|y2|}.
    The above is easy to show as a CFL. We then union this with odd length and we have L1 complement.
  6. Closure of CFLs under substitution and intersection with Regular
  7. Decision problems for CFLs: is L(G) empty or finite/infinite are fine;
    Checking ambiguity, equality to Sigma*,  equivalence and non-empty intersection with another CFL are not
Assignment #2

See Webcourses (Assignment # 2) for description
Sample of Similar Problems with Solutions

Due: 2/6 (Key)

Week#4: (1/28, 1/30) -- Computability Theory
  1. Insights from intro to computability material
  2. Basic notions of computability and complexity
  3. Existence of unsolvable problems (counting and diagonalization)
  4. Solved, solvable (decidable, recursive), unsolved, unsolvable, re, non-re
  5. Hilbert's Tenth
  6. Undecidable problems made a bit more concrete
  7. Lots about problems and their complexity
  8. Halting Problem (HALT) is re, not decidable
  9. Set of algorithms (TOT) is non-re
  10. Halting Problem seen as fun
  11. Some consequences of non-re nature of algorithms
  12. Models of computation
  13. Systems related to FRS (Petri Nets, Vector Addition, Abelian Semi-Groups)
  14. RM simulated by Ordered FRS
  15. Primitive Recursive Functions (prf)
  16. Initial functions
  17. Closure under composition and recursion
  18. Primitive recursive functions SNAP, TERM, STP and VALUE
  19. Primitive Recursive Function in detail
  20. Addition and multiplication examples
  21. Sample functions and predicates
  22. Closure under cases
  23. Bounded minimization
  24. Arithmetic fuctions that use bounded search
  25. Pairing functions
  26. Limitations of primitive recursive
  27. mu-recursion and the partial recursive functions
  28. Notions of instantaneous descriptions
  29. Encodings
  30. Equivalence of models
  31. TMs to Register Machines
  32. RM to Factor Replacement Systems

Week#5: (2/4, 2/6) -- Computability Theory
  1. Factor Replacement to Recursive Functions
  2. Gory details on FRS to REC
  3. Universal machines
  4. Recursive Functions to TMs
  5. Consequences of equivalence
  6. Review Undecidability (Halting Problem, shown by diagonalization)
  7. RE sets and semidecidability
  8. The set of all re sets W0, W1, W2, ...
  9. Enumeration Theorem
  10. The set K = { n | n is in the n-th re set } = { n | n is in Wn } is re, non-recursive
  11. The set K0 = HALT = { <n,x> | x is in the n-th re set }
  12. Alternative characterizations of re sets
  13. Parameter Theorem (aka Sm,n Theorem)
    Assignment #3

    See Webcourses (Assignment # 3) for description
    Sample of Similar Problems with Solutions

    Due: 2/18 (Key)

Week#6: (2/11, 2/13) -- Computability Theory
  1. Quantification and re sets
  2. Quantification and Co-re sets
  3. Diagonalization revisited (set of algorithms is non-re and K0 (Lu) = HALT is non-rec)
  4. Reduction
  5. Classic sets Ko (Lu), NON-EMPTY (Lne), EMPTY (Le)
  6. Reduction from Ko that shows undecidability of K, HasZero, IsNonEmpty
  7. Complete re set (K and K0 as examples)
  8. Note: To be re-complete a set must be re
  9. Reduction from Ko that shows undecidability of K, HasIndentity, TOTAL, IsZero, IsEmpty, IsIdentity
  10. Equivalence of certain re sets (K, HasZero, IsNonEmpty, HasIndentity) to Ko
  11. Equivalence of certain non-re sets (IsZero, IsEmpty, IsIdentity) to TOTAL
  12. Quantification of Non-re, Non-Co-re sets
  13. Reducibility and degrees (many-one, one-one, Turing)
  14. Hierarchy or RE equivalence class (m-1 and 1-1 degrees)
  15. Rice's Theorem

        Assignment #4

    See Webcourses (Assignment # 4) for description
    Sample with key

        Due: 2/25 (Key)

Week#7: (2/18, 2/20) -- Computability Theory
  1. "Picture" proofs for Rice's Theorem
  2. Constant Time and Mortal Machines
  3. Introduction to rewriting systems (Thue, Post)
  4. Semi-Thue systems
  5. Word problems
  6. Simulating Turing Machine by Semi-Thue System
  7. Simulating by Thue Systems
  8. Post Canonical Forms
  9. Post Correspondence Problem
  10. Grammars and re sets
  11. Unsolvable problems related to context-free grammars/languages
  12. Ambiguity of CFGs
  13. Non-Emptiness of CFL Intersections
  14. Context-Sensitive Grammars and Unsolvability Results
  15. Valid (CSL) and Invalid Traces (CFL)
  16. Intersection and Quotients of CFLs
  17. Details on Valid (CSL) and Invalid Traces (CFL)
  18. Intersection of CFLs revisited
  19. Quotients of CFLs revisited
  20. Type 0 grammars and Traces
  21. L =  S*  for L a Regular or CFL
  22. L=L^2 for L a CFL
  23. Finite Convergence
  24. Finite Power Problem for CFLs


Week#8: (2/26, 2/28) -- Computability Theory
  1. Summary of Grammar Results
  2. Revisit Set Real-Time (Constant-Time)
  3. Real-Time and Mortal Machines
  4. Finite Power Problem for CFLs
  5. Closure properties for re and recursive sets
  6. Propositional Calculus
  7. Axiomatizable Fragments
  8. Unsolvability for Membership in Fragments of Diadic Partial Implicational Propositional Calculus
  9. Review session and sample exams
  10. Exam Topics
  11. Sample exam1; Sample exam1 key
  12. Sample exam2; Sample exam2 key
  13. Key to Samples from Notes
  14. Yet Other Examples (Focused on Formal Languages and Automata Theory)
  15. Yet Other Examples key (Focused on Formal Languages and Automata Theory)
  16. Midterm Legal Cheat Sheet

Week#9: (3/3, 3/5) -- Complexity Theory

  1. Midterm (Tuesday)
  2. Basics of Complexity Theory
  3. Decision vs Optimization Problems (achieving a goal vs achieving min cost)
  4. Polynomial == Easy; Exponential == Hard
  5. Polynomial reducibility
  6. Verifiers versus solvers
  7. P as solvable in deterministic polynomial time
  8. NP as solvable in non-deterministic polynomial time
  9. NP as verifiable in deterministic polynomial time
  10. Concepts of NP-Complete and NP-Hard
  11. Canonical NP-Complete problem: SAT (Satisfiability)
  12. Some NP problems that do not appear to be in P: SubsetSum, Hamiltonian Path, k-Clique
  13. Million dollar question: P = NP ?
  14. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
  15. SAT is polynomial reducible to (<=P) 3SAT
  16. 3SAT as a second NP-Complete problem
  17. Integer Linear Programming

 Presentation Stage #1

                Turn in a list of team members (3 preferred)
                Turn in a citation to paper(s) being proposed as basis for paper and Presentation
                 Your paper that summarizes and highlights must be at least 6 pages,
                 double-spaced, single column

                 Sample Topics (see Sample Topics Folder)

            Due: 3/24

  Assignment #5


  Due: 3/26 (Key)


Week#11: (3/17, 3/19, (3/20 is Withdrawal Deadline)) -- Complexity Theory
  1. Note: 3/20 is the Withdraw Deadline
  2. 3SAT <=P SubsetSum
  3. SubsetSum <=P Partition
  4. Partition equivalence to SubsetSum
  5. Discussion of group presentations
  6. Reduction of 3SAT to k-Vertex Cover
  7. 3-SAT to 3-Coloring
  8. Isomophism of k-Coloring with k-Register Aloocation of live variables
  9. Scheduling problems introduced 
  10. Scheduling on multiprocessor systems
  11. Scheduling problems (fixed number of processors, minimize final finishing time)
  12. N processors, M tasks, no constraints
  13. Partition and scheduling problems
  14. Greedy heuristics
  15. 2 processor scheduling -- greedy based in list, sorted long to short, sorted short to long, optimal. Tradeoffs.
  16. Scheduling anomalies, level strategy for UET trees, level strategy for UET dags
  17. Precedences (lists, delays, preemption)
  18. Anomalies (reducing precedence, increasing processors, reducing times)
  19. Unit Execution Time: Trees, forest, anti forests
  20. UET: DAGs and m=2
  21. Midterm Key
  22. Sample Presentation (paper and abstract) from 2015
    This one was a group of two (smaller class size)
    The paper started with a 1998 thesis and brought us up to date (2015 pubs)
  23. Sample presentation (paper only) from 2014
    This was also a group of two
    The paper started with a 2011 paper and worked backwards to those from which the 2011 result built
  24. Both of the above were really well-done; for this Saturday evening, I just want
    Citation with pdf of paper that you will use to start your journey
    Brief abstract of your goals
    Team members
  25. For Final paper and presentation I would like  that the conclusion include your own take on the importance of the results relative to your own research including potential extensions. I am okay if you pick a single challenging paper and dissect it so others can understand the results and techniques. I am also fine with a journal (actually preferred) of papers that either start with a classic and bring us up to today or start with today and help us understand today's results in terms of other prior research.

Week#12: (3/24, 3/26) -- Complexity Theory
  1. Hamiltonian Path
  2. Traveling Salesman
  3. Knapsack (relation to SubsetSum), Dynamic Programming Approach
  4. Bin packing (fixed capacity, minimize number of bins)
  5. Pseudo polynomial-time solution for Knapsack using dynamic programming with changed parameters, n*W versus 2^n
  6. Reduction techniques
  7. Tiling the plane and Bounded Tiling
  8. Bounded PCP

            Assignment #6


            Due: 4/4 (Key)

Week#13: (3/31, 4/2) -- Complexity Theory
  1. You must send me preferred day of presentation by 4/5 at 6:00PM.
  2. You must send me an abstract of your presentation by 6:00 PM, two days prior to your scheduled day (one to two paragraphs)
  3. All papers and final versions of presentation slides are due as pdf files by 11:59 on 4/24
  4. co-NP
  5. P = co-P ; P contained in intersection of NP and co-NP
  6. NP-Hard
  7. QSAT as an example of NP-Hard, possibly not NP
  8. NP-Hard problems are in general functional not necessarily decision problems
  9. NP-Complete are decision problems as they are in NP
  10. NP-Easy -- these are problems that are polynomial when using an NP oracle
  11. NP-Equivalent is the class of NP-Easy and NP-Hard problems
  12. Optimization versions of SubsetSum and of K-Color
  15. ATM (Alternating NDTM)
  16. QSAT. Petri Nets, Presburger
  17. FP is functional equivalent to P; R(x,y) in FP if can provide value y for input x via deterministic polynomial time algorithm
  18. FNP is functional equivalent to NP; R(x,y) in FNP if can verify any pair (x,y) via deterministic polynomial time algorithm
  19. TFNP is the subset of FNP where a solution always exists, i.e., there is a y for each x such that R(x,y).
  20. Factoring is in TFNP, but is it in FP?
  21. P = (NP intersect Co-NP) is interesting analogue to intersection of RE and co-RE but may not hold here
  22. Validity of SubsetSum optimization reduction to SubsetSum Decision Problem Oracle
  23. It appears that TFNP does not have any complete problems!!!
  24. Sample slides from prior years -- mostly anonymized so you don't bug the authors
    (GMCP, Multiple object tracking as ILP, Self Assembly, Theorem Proving

Week#14:  (4/7, 4/9)
  1. 4/7 Presentations (In order as below; Group letters are for my convenience)
    ? (4/7)    XXX

    ? (4/7)    XXX
    ? (4/7)    XXX
    ? (4/7)    XXX
    ? (4/7)    XXX
  2. 4/9 Presentations (In order as below; Group letters are for my convenience)
    ? (4/9)    XXX

    ? (4/9)    XXX
    ? (4/9)    XXX
    ? (4/9)    XXX
    ? (4/9)    XXX

Week#15: (4/14, 4/16)

  1. 4/14 Presentations (In order as below; Group letters are for my convenience)
    ? (4/14)    XXX
    ? (4/14)    XXX
    ? (4/14)    XXX
    ? (4/14)    XXX
    ? (4/14)    XXX
  2. Final Exam Topics
  3. Sample Final Exam (Key)


Week#16:  (4/21 -- Final Exam)

  1. Due on Friday, 4/24 by midnight

Final Exam is Tuesday April 21; 1:00PM to 3:50PM in HEC-103

İ UCF (Charles E. Hughes)  -- Last Modified 2/18/2020