Complexity Theory Spring 2022 |

Computer Science

College of Engineering and Computer Science

University of Central Florida

email: charles.hughes@ucf.edu

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

**Room**: HEC-103 when we meet fasce-to-face;

**Class Zoom Link for when we meet virtually: **__https://tinyurl.com/yckpdx92__

**
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/Thursday 10:45-12:00PM

** GTA****: ** Parisa Darbar;
Contact: pdarbar@knights.ucf.edu; Use Subject COT6410

**Office
Hours: ****MW
2:00 PM-3:15 PM**

**OH
Zoom Link: ****https://tinyurl.com/y2y2lmum
**

**Required Reading: All class
notes linked from this site.**

**Recommended Reading**:

**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.**- Garey&Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1979.
- Cooper, Computability
Theory 2nd Ed., Chapman-Hall/CRC Mathematics Series,
2003.

- 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.

**Web Pages**:

Base URL: https://www.cs.ucf.edu/courses/cot6410/Spring2022

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

2021 Videos URL: OlderVideos/

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

**Exams**: Midterm and Final.

**Exam Dates (****Tentative)****: Mid
Term: Tuesday, March 15 in HEC-101**; Withdraw
Deadline: Friday, March 23; Spring Break: March 6-13; Final:
Thurs., April 28, 7:00AM-9:50AM in **HEC-101**.

**Evaluation (Tentative)**:

- Mid Term: 125 points; Final Exam: 125 points (balance between weights will be adjusted in your favor)
- Assignments: 75 points;

- Individual Paper Reviews and Presentations: 125 points
- Extra -- 50 points used to increase weight of best exam, always to your benefit
- Total Available: 500
- Grading will be A >= 90%, B+ >= 85%, B >= 80%,
C+ >= 75%, C >= 70%, D >= 50%, F < 50%; minus grades
might be used.

.

Videos from Last Year (2021) are here

The old videos for this week are: Preliminary.mp4, Intro.mp4, Day1_Trimmed.mp4, Day2_Trimmed.mp4

New Videos, as they are created will be in the Zoom Cloud Recording folder.

**Ground rules****Decision problems (HMU 1.5)**

**Solving vs checking****Procedures vs algorithms****Introduction to the theory of computation****Terminology, goals****Overview of automata (finite, pushdown, linear bounded, Turing machines)****Overview of formal languages (regular, context free, context sensitive, phrase structured)****Regular Languages (Sipser 1.1; HMU 2.1, 2.2)**

**Recognized by Deterministic finite state automata (DFA)****Closure Properties of Regular Languages (Sipser 1.2; HMU 4.2)**

**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**

**Other Formal Models for Regular Languages**

**Recognized by Deterministic finite state automata (DFA)****(Sipser 1.1; HMU 2.1, 2.2)****Recognized by Non-Deterministic finite state automata (NFA) (Sipser 1.2; HMU 2.3-2.5)**

**Lambda-Closure use in this construction**

**Denoted by Regular Expressions (Sipser 1.3; HMU 3.1-3.3)**

**Every Regular Set is a Regular Languages**

- Review material created by Prof. Jim Rogers, Earlam College
- Review material from Prof.
David Workman, UCF Retired

Financial Aid (Assignment#1)

Survey at Webcourses

Due: Friday, January 14 at 11:59 PM

**Continue Automata/Formal Languages Review**

**Every Regular Language is a Regular Set (Sipser 1.3; HMU 3.1-3.3)**

**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****State minimization using O(| Q |**^{2}) table. Note alphabet is constant size. (Sipser p. 327; HMU 4.4)

**Why is this just****O(| Q |**^{2}) cost, rather than**O(| Q |**^{3})?**More closure properties (Sipser 1.1; HMU 4.2-4.3)**

**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.**

**Closure under min and max****and discussions of various Reaching Algorithms (Depth-First Search)****Pumping Lemma for Regular Languages (Pigeon Hole Principle) (Sipser 1.4; HMU 4.1)**

**Adversarial Nature of use of PL to show a language is not Regular**

- Myhill-Nerode Theorem
(implicit in HMU 4.4)

- Right invariant equivalence relations of finite index
- Specific right invariant
equiv. relation, R
_{L}for language L

**Myhill-Nerode as proof of min DFA uniqueness**

**Myhill-Nerode as proof of min DFA uniqueness**- Myhill-Nerode as a tool to show
languages are not regular.

- The chosen language is

L = { a^{n}b^{m}| 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. - Finite State Machines
(Transducers): Mealy versus Moore Model (Sipser p. 87)

- Decision Problems for Regular Languages (HMU 3.4; HMU 4.3
- Introduction to Grammars (Regular
and CFG mainly) (Sipser 2.1;

- Regular Grammars and Regular
Languages (HMU p. 180)

**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
- Context Free Grammars (A
$\to $
x where x
$\u220a$ (V
$\bigsqcup $
$\Sigma $)*
) (Sipser 2.1; HMU 5.1)

- Use of context free grammars in
parsing and notion of Ambiguity (Sipser 2.1; HMU 5.2, 5.4)

- Bottom-Up (Shift-Reduce and conflicts)
- Top-Down (Predictive and guessing
-- recursive descent)

- Review of reduced CFGs (HMU 7.1)

- Remove Rules: Null, Unit,
Non-Productive, Unreachable (order of removal matters)

- Chomsky Normal Form (CNF) (Sipser
2.1; HMU 7.1)

- A -> a and A -> BC are only
allowed forms

- The use of CNF in the
Cocke-Kasami-Younger O(N
^{3}) parsing of CFLs generated by CNFs (HMU 7.4)

- Bottom-Up technique

- Great Example of the value of Dynamic Programming
- Pumping Lemma for CFLs (Sipser 2.3;
HMU 7.2)

- Show L = { a
^{n}b^{n}c^{n}| n i> 0 } and {L2 = { ww | w is in {a,b}^{+}} are not CFLs - CSG for L

- Non-closure of CFLs under
intersection and complement (Sipser 2.3)

**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.- Decision problems for CFLs:
is L(G) empty or finite/infinite are fine (Sipser 4.1; HMU
7.4)

Assignment #2See Webcourses (Assignment # 2) for description

Sample of Similar Problems with Solutions

Due: 2/8 (Key)

- Show L = { a
^{n}b^{n}c^{n}| n i> 0 } and {L2 = { ww | w is in {a,b}^{+}} are not CFLs - CSG for L

- Non-closure of CFLs under
intersection and complement (Sipser 2.3)

**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.- Decision problems for CFLs: is L(G) empty or finite/infinite are fine (Sipser 4.1; HMU 7.4)
- Closure of CFLs under
substitution and intersection with Regular (HMU 7.3)

- Checking ambiguity, equality to Sigma*, equivalence and non-empty intersection with another CFL are nasty
- Very Basic Material on
Context Sensitive Grammars (CSG) and Linear Bounded Automata
(LBA)

- Show L1 = { a
^{n}b^{n}c^{n}| n i> 0 } and L2 = { ww | w is in {a,b}^{+}} are CSLs

- Insights from intro to
computability material

**Basic notions of computability and complexity****Existence of unsolvable problems (counting and diagonalization)****Solved, solvable (decidable, recursive), unsolved, unsolvable, re, non-re****Hilbert's Tenth**- Undecidable problems made a bit more concrete
**Lots about problems and their complexity**- Halting Problem (HALT) is re, not decidable
- Set of algorithms (TOT) is non-re
- Halting Problem seen as fun
**Some consequences of non-re nature of algorithms**

**Models of computation**- Turing machines

- Register machines
- Factor replacement systems (FRS)
- Originally introduced by John Conway, "Unpredictable Iterations," Proceedings of the 1972 Number Theory Conference (1972), pp. 49-52
- Google Fractran for more information on Conway's
fractional computation systems

Weisstein, Eric W. "FRACTRAN." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FRACTRAN.html - The 3x+1 problem https://arxiv.org/pdf/math/0309224.pdf
**Systems related to FRS (Petri Nets, Vector Addition, Abelian Semi-Groups)****RM simulated by Ordered FRS****Primitive Recursive Functions (prf)****Initial functions****Closure under composition and recursion****Primitive recursive functions SNAP, TERM, STP and VALUE****Primitive Recursive Function in detail****Addition and multiplication examples****Sample functions and predicates****Closure under cases****Bounded minimization****Arithmetic fuctions that use bounded search****Pairing functions**- Limitations of primitive recursive
**mu-recursion and the partial recursive functions****Notions of instantaneous descriptions****Encodings****Equivalence of models****TMs to Register Machines****RM to Factor Replacement Systems****Factor Replacement to Recursive Functions**- Gory details on FRS to REC
**Universal machines**- Recursive Functions to TMs
**Consequences of equivalence**

See Webcourses (Assignment # 3) for description

Sample of Similar Problems with Solutions

**Due: 2/22 (Key)**

- Recursive Functions to TMs
(completes equivalence)

**Consequences of equivalence****The primitive recursive predicate STP and function VALUE**

**Review Undecidability (Halting Problem, shown by diagonalization)****RE sets and semidecidability****Enumeration Theorem:**The set of all re sets W_{0}, W_{1}, W_{2}, ...**The set K = { n | n is in the n-th re set } = { n | n is in W**_{n}} is re, non-recursive- The set K
_{0}= HALT = { <n,x> | x is in the n-th re set } **Alternative characterizations of re sets****Parameter Theorem (aka Sm,n Theorem)****Quantification and re sets****Quantification and co-re sets****Quantification and non-re / non-co-re sets****Reduction****Classic sets**)**Halt = Ko**= Lu, NON-EMPTY (Lne), EMPTY (Le**Reduction from****Ko****that shows undecidability of K, HasZero,****IsNonEmpty****Complete re set (K and**K_{0}**as examples)****Note: To be re-complete a set must be re****Reduction from****Ko****to****HasIndentity,****TOTAL, IsZero, IsEmpty, IsIdentity**- Equivalence of certain re
sets (K, HasZero, IsNonEmpty
**, HasIndentity**) to**Ko** - Equivalence of certain non-re sets (IsZero, IsEmpty, IsIdentity) to TOTAL
**Reducibility and degrees (many-one, one-one, Turing)**- Hierarchy or RE equivalence class (m-1 and 1-1 degrees)
**Rice's Theorem**

**
Assignment #4**

See Webcourses
(Assignment # 4) for description

Sample with key

**"Picture" proofs for Rice's Theorem****Constant Time and Mortal Machines****Introduction to rewriting systems (Thue, Post)****Union, intersection, complement**for recursive, re and non-re sets (can be, cannot be)**Rewriting systems****Post Canonical Forms****Thue and Semi-Thue systems (relation to group theory)**

**Word problems (Semi-Thue and Thue) and equivalence problems (Thue)****Simulating Turing Machine by Semi-Thue System****Simulating Turing Machines by Thue Systems****Grammars and re sets****Brief introduction to Post Correspondence Systems and Relation to Semi-Thue Systems****Post Correspondence Problem (in detail)**

**Unsolvable problems related to context-free grammars/languages****Ambiguity of CFGs****Non-Emptiness of CFL Intersections****Context-Sensitive Grammars and Unsolvability Results****Valid (CSL) and Invalid Traces (CFL)****Details on Valid (CSL) and Invalid Traces (CFL)****Intersection of CFLs revisited****Quotients of CFLs**

**Type 0 grammars and Traces****L = Sigma* for L a Regular or CFL****L = L^2 for L a CFL****Summary of Grammar Results**

- Review session and sample exams
- Exam Topics

- Sample exam1; Sample exam1
key

- Sample exam2; Sample exam2 key
- Key to Samples from Notes
- Yet Other Examples (Focused on Formal Languages and Automata Theory)
- Yet Other Examples key (Focused on Formal Languages and Automata Theory)
- Midterm Legal Cheat Sheet
- Basics of Complexity Theory
- Decision vs Optimization Problems (achieving a goal vs achieving min cost)
- Polynomial == Easy; Exponential == Hard
- Polynomial reducibility
**Verifiers versus solvers**- P as solvable in deterministic polynomial time
- NP as solvable in non-deterministic polynomial time
- NP as verifiable in deterministic polynomial time
- Concepts of NP-Complete and NP-Hard
- Canonical NP-Complete problem: SAT (Satisfiability)
- Some NP problems that do not appear to be in P: Graph Coloring, Vertex Cover, SubsetSum
- Million dollar question: P = NP ?
- Boolean expressions:
Tautologies, Satisfiability, Truth Tables

- Axiomatic Systems for
propositional logic: Substitution and modus ponens versus
refutation/resolution

- Unsolvability of deducibility in fragments of propositional calculus

**Week#10 (3/15, 3/17: Midterm Exam and **Complexity
Theory

**Midterm (Tuesday, March 15 in HEC-101)****Midterm Key**- More Comments on unsolvability of deducibility in fragments of propositional calculus
- Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
- SAT is polynomial reducible
to (<=
_{P}) 3SAT - 3SAT as a second NP-Complete problem
- Integer Linear Programming
- 3SAT <=
_{P}SubsetSum - SubsetSum <=
_{P }Partition **Partition****equivalence to SubsetSum**

- Discussion of presentations
- Reduction of 3SAT to k-Vertex Cover
**3-SAT to 3-Coloring**- Isomophism of k-Coloring with k-Register Allocation of live variables
**Scheduling problems introduced**- Scheduling on multiprocessor systems
- Scheduling problems (fixed number of processors, minimize final finishing time)
- N processors, M tasks, no constraints
- Partition and scheduling problems
- Greedy heuristics
- 2-processor scheduling -- greedy based on list, sorted long to short, sorted short to long, optimal. Tradeoffs.
- Precedences (lists, delays, preemption)
- Anomalies (reducing precedence, increasing processors, reducing times)
- Unit Execution Time: Trees, forest, anti forests
- UET: DAGs and m=2
**Hamiltonian Path****Traveling Salesman****Knapsack (relation to SubsetSum), Dynamic Programming Pseudo-polynomial Solution****Bin packing (fixed capacity, minimize number of bins)****Pseudo polynomial-time solution for Knapsack using dynamic programming with changed parameters,**

**n*W versus 2^n but W = 2^log(W). This kind of problem is called Weak NP Complete. I'll chat about that later.**

**You will each, individually, develop a paper and a presentation, based on an existing research paper, just as if you had to present to your peers and advisors. In addition to presenting the results and the way in which these were proven, you should comment on the paper's importance, readability, and replicability, and even its validity if you question that, just as if you were a journal or conference reviewer. Your report must be a tutorial on the topic of the paper so those with less time to delve into the paper can get a strong sense of the results and the context of those results. Specifying new open problems that you see as interesting is also a goal, but may not be attainable for some of these. The length of your paper****is 6 to 12 pages double-spaced, 1" margins all around, using either Times Roman or Calibri 11 point, or Arial 10-point. The references are in addition to the narrative and appear on separate pages that do not count against the 6 to 12-page limit. Images may be used but if the total number of images exceeds a page, then all past that one-page aggregate will lead to a requirement for additional text. The presentation slides must be designed to support your 8 to 10-minute video. This means that there are likely 10 to 15 slides.**- Towards the end of the
semester you give a presentation to a small group of other
students 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.

- I have placed about 55 sample papers at Sample Topics. 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."
- 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.
- I also put out a folder that 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 presentations you provide.

**Due: 4/22**

**Assignment #5**

Sample with Key

- Tiling the plane and Bounded Tiling
- Bounded PCP

- Co-NP
- Reduction techniques
- P = co-P ; P contained in intersection of NP and co-NP
- NP-Hard
- QSAT as an example of NP-Hard, possibly not NP
- NP-Hard problems are in general functional not necessarily decision problems
- NP-Complete are decision problems as they are in NP
- NP-Easy -- these are problems that are polynomial when using an NP oracle
- 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
- Optimization versions of SubsetSum and K-Color
**Validity of SubsetSum optimization reduction to SubsetSum Decision Problem Oracle**

**2SAT****(linear time complexity)****Uniform Min-1 is NP Equivalent****Triangle Strip versus Triangle List****Weakly versus Strongly NP-Hard/NP-Complete**

**Assignment #6**

Sample with Key

**Due: 4/19 (Key)**

- PSPACE, NPSPACE, CO-PSPACE,
PSPACE-COMPLETE

- EXPSPACE, EXPTIME, NEXPTIME
- ATM (Alternating NDTM)
- QSAT, Petri Nets, Presburger
- Why does PS
**PA**CE = NPSPACE? Key is Savitch's Theorem

**PSPACE-Complete problems (CSL membership, QSAT)**- FP is functional equivalent to P; R(x,y) in FP if can provide value y for input x via deterministic polynomial time algorithm
- FNP is functional equivalent to NP; R(x,y) in FNP if can verify any pair (x,y) via deterministic polynomial time algorithm
- 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)

- Factoring is in TFNP, but is it in
FP?

- If TFNP in FP then TFNP = FP
**P = (NP intersect Co-NP) is interesting analogue to intersection of RE and co-RE but may not hold here****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)****Khot's Conjecture and its implications**

**Week#14:**** (4/12, 4/14) **More Computability Notes

**Cleanups (topics that were left hanging earlier)****Mortality Problem****Constant Execution Time****Extensions of Finite Power Property**- Final Exam Topics
- More stuff for final

- Sample Final Exam (Key)
**Exam Review (emphasis on Formal Languages and Computability topics)**

- Exam Review (emphasis on
complexity topics and sample exam questions)

- On 4/21 we will have the breakout
sessions in which you give your presentations and hear those of
a few of your fellow students (typically five per breakout
room). These will be set up prior to the 21st.

- Rules of the game and group composition for Breakout Rooms on the 21st.
**Breakout Room Videos**

**Assignment #7**

**Due: 4/23**

**Week#16: **** ****(4/28
-- Final Exam in HEC-101)**

**I****will**run a help session on Tuesday, 4/26 at the normal class time

- All Project Videos, Papers, and
Presentations are Due on Friday, 4/
**22**by midnight **Final Exam****is Thursday April 28; 7:00AM to 9:50AM**

©**4/23/**2022