Complexity Theory Spring 2020 |

Computer Science

University of Central Florida

email: charles.hughes@ucf.edu

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

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

- Hopcroft, Motwani&Ullman, Intro to Automata Theory, Languages and Computation 3rd Ed., Prentice-Hall, 2006.
- Oded Goldreich, Computational
Complexity:
A Conceptual Approach, Cambridge University Press,
2008.

Draft available at http://www.wisdom.weizmann.ac.il/~/oded/cc-drafts.html - Oded Goldreich, P, NP, and
NP-Completeness: The Basics of Complexity Theory,
Cambridge University Press, 2010.

Draft available at http://www.wisdom.weizmann.ac.il/~/oded/bc-drafts.html - Arora&Barak, Computational
Complexity:
A Modern Approach, Cambridge University Press, 2009.

Draft available at http://www.cs.princeton.edu/theory/complexity/ - Sipser, Introduction to the Theory of Computation 3rd Ed., Cengage Learning, 2013.

**Web Pages**:

Base URL: http://www.cs.ucf.edu/courses/cot6410/Spring2020

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:00PM3:50PM

**Evaluation (Tentative)**:

- Mid Term 125 points; Final Exam 200 points (balance between weights will be adjusted in your favor)
- Assignments 75 points; Paper and Presentation 75 points
- Extra -- 25 points used to increase weight of best exam, or maybe presentation, 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.

.

**Ground rules****Decision problems****Solving vs checking****Procedures vs algorithms****Introduction to theory of computation****Terminology, goals and some historical perspective****Review of automata (finite, pushdown, linear bounded, Turing machines)****Review of formal languages (regular, context free, context sensitive, phrase structured)**- Review material created by Prof. Jim Rogers, Earlam College
- Review material from Prof. Workman, UCF

Financial Aid (Assignment#1)

Survey at Webcourses

Due: Friday, January 10 at 11:59 PM

**Continue Automata/Formal Languages Review**- 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. - Review of reduced CFGs
- Chomsky Normal Form (CNF)

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

- Pumping Lemma for CFLs

- Show L = { ww | w is in {a,b}
^{+}} is not a CFL - CSG for L

- Non-closure of CFLs under
intersection and complement

- 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. - Closure of CFLs under substitution and intersection with Regular
- 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 #2See Webcourses (Assignment # 2) for description

Sample of Similar Problems with Solutions

Due: 2/6 (Key)

- 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. http://mathworld.wolfram.com/FRACTRAN.html - The 3x+1 problem http://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****Review Undecidability (Halting Problem, shown by diagonalization)****RE sets and semidecidability****The set of all re sets W**_{0}, W_{1}, W_{2}, ...**Enumeration Theorem****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)**

See Webcourses (Assignment # 3) for description

Sample of Similar Problems with Solutions

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

**Quantification and re sets****Quantification and Co-re sets****Diagonalization revisited (set of algorithms is non-re and**K_{0}**(Lu)**= HALT**is non-rec)****Reduction****Classic sets**)**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****that shows undecidability of K,****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
- Quantification of Non-re,
Non-Co-re sets

**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)****Semi-Thue systems****Word problems****Simulating Turing Machine by Semi-Thue System****Simulating by Thue Systems****Post Canonical Forms****Post Correspondence Problem****Grammars and re sets****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)****Intersection and**Quotients of CFLs**Details on Valid (CSL) and Invalid Traces (CFL)****Intersection of CFLs revisited****Quotients of CFLs revisited****Type 0 grammars and Traces****L = S* for L a Regular or CFL****L=L^2 for L a CFL**- Finite Convergence
**Finite Power Problem for CFLs**

**Summary of Grammar Results**

- Revisit Set Real-Time (Constant-Time)
**Real-Time and Mortal Machines****Finite Power Problem for CFLs**- Closure properties for re and
recursive sets

- Propositional Calculus
- Axiomatizable Fragments
- Unsolvability for Membership in Fragments of Diadic Partial Implicational Propositional Calculus
- 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

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

**Midterm (Tuesday)**- 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: SubsetSum, Hamiltonian Path, k-Clique
- Million dollar question: P = NP ?
- 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

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

**
Assignment #5**

**
****TBD**

- Note: 3/20 is the Withdraw Deadline
- 3SAT <=
_{P}SubsetSum - SubsetSum <=
_{P }Partition **Partition****equivalence to SubsetSum**- Discussion of group presentations
- Reduction of 3SAT to k-Vertex Cover
**3-SAT to 3-Coloring**- Isomophism of k-Coloring with k-Register Aloocation 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 in list, sorted long to short, sorted short to
long, optimal. Tradeoffs.

**Scheduling anomalies, level strategy for UET trees, level strategy for UET dags**- Precedences (lists, delays, preemption)
- Anomalies (reducing precedence, increasing processors, reducing times)
- Unit Execution Time: Trees, forest, anti forests
- UET: DAGs and m=2
- Midterm Key
- 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)

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

- Hamiltonian Path
- Traveling Salesman
- Knapsack (relation to SubsetSum), Dynamic Programming Approach
**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
- Reduction techniques
- Tiling the plane and Bounded Tiling
- Bounded PCP

**Assignment #6**

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

- You must send me preferred day
of presentation by 4/5 at 6:00PM.

- The days to choose from are 4/7, 4/9, 4/14, 4/16.
- You must send me an abstract of your presentation by 6:00 PM, two days prior to your scheduled day (one to two paragraphs)
- The abstract must include title and team member names
- It is designed so everyone is mentally prepared for your
presentation

- All papers and final versions
of presentation slides are due as pdf files by 11:59 on 4/24

- Your papers must include one or two questions you would ask of your audience
- I would also like the files (word, power point, tex, etc.) used to create these in a zip or rar
**co-NP**- 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 of K-Color

- Clean-up (PSPACE, NPSPACE,
CO-PSPACE, PSPACE-COMPLETE)

- EXPSPACE, EXPTIME, NEXPTIME
- ATM (Alternating NDTM)
- QSAT. Petri Nets, Presburger

- 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
- Validity of SubsetSum
optimization reduction to SubsetSum Decision Problem Oracle

- 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)
- Sample slides from prior years -- mostly anonymized so you
don't bug the authors

(GMCP, Multiple object tracking as ILP, Self Assembly, Theorem Proving

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

- 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 **Final Exam Topics****Sample Final Exam (Key)**

**Due on Friday, 4/24 by midnight**