Complexity Theory Spring 2021

Charles E. Hughes Computer ScienceUniversity of Central Florida

email: charles.hughes@ucf.edu

Structure: TR 0900-1015 (9:00AM-10:15AM); Virtual; 28 class periods, each 75 minutes long.

Class Zoom Link: https://tinyurl.com/y5qxkqz5

Go To Week
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
, 15, 16

Instructor: Charles Hughes; Contact: charles.hughes@ucf.edu; Use Subject COT6410
Office Hours: Tuesday 10:45AM-11:45AM; Thursday 12:15PM-1:30PM
OH Zoom Link: https://tinyurl.com/y3ffvbm3

GTA:  Daniel Daniel Gibney; Contact: dangibney@knights.ucf.edu; Use Subject COT6410
Office Hours: MW 1:30PM-3:00PM

Required Reading: All class notes linked from this site.

:

• Sipser, Introduction to the Theory of Computation 3rd Ed., Cengage Learning, 2013.
• Hopcroft, Motwani&Ullman, Intro to Automata Theory, Languages and Computation 3rd Ed., Prentice-Hall, 2006.
• Cooper, Computability Theory 2nd Ed., Chapman-Hall/CRC Mathematics Series, 2003.
• Garey&Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1979.
• Davis, Sigal&Weyuker, Computability, Complexity and Languages 2nd Ed., Acad. Press (Morgan Kaufmann), 1994.
• Papadimitriou & Lewis, Elements of the Theory of Computation, Prentice-Hall, 1997.
• Bernard Moret, The Theory of Computation, Addison-Wesley, 1998.
• Oded Goldreich, Computational Complexity: A Conceptual Approach, Cambridge University Press, 2008.
• Oded Goldreich, P, NP, and NP-Completeness: The Basics of Complexity Theory, Cambridge University Press, 2010.
• Arora&Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

Assignments: 6 for sure and maybe a seventh; Paper + Video Presentation with Slides

Exams: Midterm and Final.

Exam Dates (Tentative): Mid Term: Thursday, March 11; Withdraw Deadline:Friday, March 26; Spring Break: April 11-18; Final: Thurs., April 29, 7:00AM-9:50AM

Evaluation (Tentative):

1. Mid Term: 125 points; Final Exam: 125 points (balance between weights will be adjusted in your favor)
2. Assignments: 75 points;
3. Individual Paper Reviews and Presentations: 125 points
4. Extra -- 50 points used to increase weight of best exam,  always to your benefit
5. Total Available: 500
6. 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/12, 1/14) -- Syllabus; About Me; Preliminaries; 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. Overview of automata (finite, pushdown, linear bounded, Turing machines)
8. Overview of formal languages (regular, context free, context sensitive, phrase structured)
9. Regular Languages
• Recognized by Deterministic finite state automata (DFA)
• Recognized by Non-Deterministic finite state automata (NFA)
• Lambda-Closure use in this construction
• Denoted by Regular Expressions (Regular Sets = Regular Languages)
• Rijk construction
• State ripping
• Solutions to Sets of Simultaneous Regular Equations (Arden's Theorem)
• R = Q+RP, P does not contain lambda, then R = QP* is unique solution
10. Closure Properties of Regular Languages
• Complement
• Union, Intersection, Difference, Exclusive Union, etc.
• Based on parallel DFA construction with only Final States changing
• Reversal
• Motivates Non-Determinism when we reverse orientation of directed edges
11. Review material created by Prof. Jim Rogers, Earlam College
12. Review material from Prof. David Workman, UCF Retired

Financial Aid (Assignment#1)

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

Week#2: (1/19, 1/21) -- Formal Languages and Automata Theory
1. Continue Automata/Formal Languages Review
2. State minimization using O(| Q | 2) table. Note alphabet is constant size.
• Why is this just O(| Q | 2) cost, rather than O(| Q | 3)
3. More closure properties
• Reversal and regular equations
• Substitution
• Quotient using NFA
• Quotient redone use meta technique based on substitution and intersection with Regular Sets
• Meta technique for Init (Prefix), Last, (Suffix) Mid (Substring), Exterior, etc.
4. Closure under min and max and discussions of various Reaching Algorithms (Depth-First Search)
5. Pumping Lemma for Regular Languages (Pigeon Hole Principle)
• Adversarial Nature of use of PL to show a language is not Regular
6. Myhill-Nerode Theorem
• Right invariant equivalence relations of finite index
• Specific right invariant equiv. relation, RL for language L
7. Myhill-Nerode as proof of min DFA uniqueness
8. Myhill-Nerode as a tool to show languages are not regular.
9. 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.
10. Finite State Machines (Transducers): Mealy versus Moore Model
11. Decision Problems for Regular Languages
12. Introduction to Grammars (Regular and CFG mainly)
13. Regular Grammars and Regular Languages
• Rules of Form A a; A aB; A $\lambda$ Define Right Linear Grammars
• Conversion of DFA to Equivalent Right Linear Grammar
• Conversion of Right Linear Grammar to Equivalent NFA
• Equivalence of Right and Left Linear Grammars as Generators of Languages
• Why We Cannot Mix Right and Left Linear Grammars and stay in Regular Languages
• Extended Right and Left Linear grammars Using String of Terminals

Week#3: (1/26, 1/28) -- Formal Languages and Automata Theory
1. Context Free Grammars (A $\to$ x where x $∊$ (V $\bigsqcup$ $\Sigma$)* )
2. Use of context free grammars in parsing and notion of Ambiguity
• Bottum-Up (Shift-Reduce and conflicts)
• Top-Down (Predictive and guessing -- recursive descent)
3. Review of reduced CFGs
• Remove Rules: Null, Unit, Non-Productive, Unreachable (order of removal matters)
4. Chomsky Normal Form (CNF)
• A -> a and A -> BC are only allowed forms
5. The use of CNF in the Cocke-Kasami-Younger O(N3) parsing of CFLs generated by CNFs
• Bottum-Up technique
• Great Example of the value of Dynamic Programming
6. Pumping Lemma for CFLs
7. Show L = { ww | w is in {a,b}+ } is not a CFL
8. CSG for L
9. Non-closure of CFLs under intersection and complement
10. 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 strings and we have L1 complement.
11. Closure of CFLs under substitution and intersection with Regular
12. 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/9 (Key)

¡

Week#4: (2/2, 2/4) -- 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
• Turing machines
• Register machines
• Factor replacement systems (FRS)
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/9, 2/11) -- 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/23 (Key)

Week#6: (2/16, 2/18) -- 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: 3/2 (Key)

Week#7: (2/23, 2/25) -- Computability Theory
1. "Picture" proofs for Rice's Theorem
2. Constant Time and Mortal Machines
3. Introduction to rewriting systems (Thue, Post)
4. Union, intersection, complement for recursive, re and non-re sets (can be, cannot be)
5. Rewriting systems
6. Post Canonical Forms
7. Thue and Semi-Thue systems (relation to group theory)
8. Word problems (Seni-Thue and Thue) and equivalence problems (Thue)
9. Brief introduction to Post Correspondence Systems and Relation to Semi-Thue Systems

Week#8: (3/2, 3/4) -- Computability Theory
1. Simulating Turing Machine by Semi-Thue System
2. Simulating Turing Machines by Thue Systems
3. Grammars and re sets
4. Post Correspondence Problem (in detail)
5. Unsolvable problems related to context-free grammars/languages
6. Ambiguity of CFGs
7. Non-Emptiness of CFL Intersections
8. Context-Sensitive Grammars and Unsolvability Results
9. Valid (CSL) and Invalid Traces (CFL)
10. Intersection and Quotients of CFLs
11. Details on Valid (CSL) and Invalid Traces (CFL)
12. Intersection of CFLs revisited
13. Quotients of CFLs revisited
14. Type 0 grammars and Traces
15. L =  Sigma*  for L a Regular or CFL
16. L=L^2 for L a CFL
17. Summary of Grammar Results
18. Review session and sample exams
19. Key to Samples from Notes
20. Yet Other Examples (Focused on Formal Languages and Automata Theory)
21. Yet Other Examples key (Focused on Formal Languages and Automata Theory)

Week#9: (3/9, 3/11) -- Midterm Review and Exam

1. Review (Tuesday)
2. Midterm (Thursday)

Week#10 (3/16, 3/18: Complexity Theory

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

Week#11: (3/23, 3/25, (3/26 is Withdrawal Deadline)) -- Complexity Theory
1. Note: 3/26 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 Allocation 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. Midterm Key
21. Towards the end of the semester you give a presentation to a small group of other studesnt and they to you. This will be done in a breakout Zoom session where your presentation and any questions/answers are captured. You may, if you wish, create the presentation in advance and share a video, but you need to be there to participate in the Q&A and to hear other students' presentations. To do this, I assume you all have access to a webcam and use Zoom or a similar tool that captures your slides and you in one extended screen. Let me know if you lack a webcam. Note that you will be asked to provide some brief feedback to me on the papers of your fellow students taking part in teh same breakout.
22. I will place about 50 sample papers out there at SampleTopics (not live yet). You may choose from any of these except for ones that have already been taken. You may also choose your own separate from these with permission from me. In general, the minimum page length in IEEE 2-column format is 8 pages or 10 pages in single column, single-spaced layout. The prefix CLAIMED_NAME means NAME has already chosen that. Please send me an email to assure you succeed in making your "claim."
23. Realize that many of these suggested papers will be from arXiv and, while arXiv is a fantastic source, it is not refereed so if you question the validity of some result, that is actually a reasonable outcome so long as you present their approach and your counterarguments just as if you were a reviewer.
24. This folder (to be made live later) contains some examples (papers and presentations) from past semesters.

Final Paper and PowerPoint

Read above. Its weight is 125 points. The split is nominally 75 for the paper and 50 for your presentation
and feedback on other's presentations you provide.

Due: 4/23

Assignment #5

See Webcourses (Assignment # 5) for description
Sample with Key

25.  Due: 4/6 (Key)

Week#12: (3/30, 4/1) -- Complexity Theory
1. Unit Execution Time: Trees, forest, anti forests
2. UET: DAGs and m=2
3. Hamiltonian Path
4. Traveling Salesman
5. Knapsack (relation to SubsetSum), Dynamic Programming Approach
6. Bin packing (fixed capacity, minimize number of bins)
7. Pseudo polynomial-time solution for Knapsack using dynamic programming with changed parameters, n*W versus 2^n
8. Tiling the plane and Bounded Tiling
9. Bounded PCP
10. Co-NP
11. Reduction techniques
12. P = co-P ; P contained in intersection of NP and co-NP
13. NP-Hard
14. QSAT as an example of NP-Hard, possibly not NP
15. NP-Hard problems are in general functional not necessarily decision problems
16. NP-Complete are decision problems as they are in NP
17. NP-Easy -- these are problems that are polynomial when using an NP oracle
18. NP-Equivalent is the class of NP-Easy and NP-Hard problems
• In essence this is functional equivalent of NP-Complete but also of co-NP Complete
• NP-Equivalent uses a Turing machine polynomial time reduction so just uses rather than accepts answers from oracle
19. Optimization versions of SubsetSum and K-Color

Assignment #6

See Webcourses (Assignment # 6) for description
Sample with Key

Due: 4/20 (Key)

Week#13: (4/6, 4/8) --
1. Clean-up (PSPACE, NPSPACE, CO-PSPACE, PSPACE-COMPLETE)
2. EXPSPACE, EXPTIME, NEXPTIME
3. ATM (Alternating NDTM)
4. QSAT. Petri Nets, Presburger
5. Validity of SubsetSum optimization reduction to SubsetSum Decision Problem Oracle
6. 2SAT (linear time complexity)
7. Uniform Min-1 is NP Equivalent
8. Propositional Calculus
Axiomatizable Fragments
Unsolvability for Membership in Fragments of Diadic Partial Implicational Propositional Calculus
9. Finite Convergence
Finite Power Problem for CFLs

Revisit Set Real-Time (Constant-Time)

Real-Time and Mortal Machines

Week#14:  Spring Break

Week#15: (4/20, 4/22)

1. FP is functional equivalent to P; R(x,y) in FP if can provide value y for input x via deterministic polynomial time algorithm
2. FNP is functional equivalent to NP; R(x,y) in FNP if can verify any pair (x,y) via deterministic polynomial time algorithm
3. 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).
• Task of a TFNP algorithm is to find a y, given x, such that R(x,y)
• Unlike FNP, the search for a y is always successful
• FNP properly contains TFNP contains FP (we don't know if proper)
4. Factoring is in TFNP, but is it in FP?
• If TFNP in FP then TFNP = FP
5. P = (NP intersect Co-NP) is interesting analogue to intersection of RE and co-RE but may not hold here
6. It appears that TFNP does not have any complete problems!!!
• The deal is that there is no known recursive enumeration of TFNP but there is of FNP
• This is similar to total versus partially recursive functions (analogies are everywhere)
7. On 4/22 we will have the breakout sessions in which you give your presentations and hear those of a few other of your fellow students (typically five or six per breakout room)
8. Final Exam Topics

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

1. I will run  a help session on Tuesday, 4/27 at the normal class time
2. All Project Papers and Presentations are Due on Tuesday, 4/23 by midnight
3. Final Exam is Thursday April 29; 7:00AM to 9:50AM; There may also be a take home component