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 125 points (balance between weights will be adjusted in your favor)
- Assignments 75 points; Independent Paper Reviews and Presentations 125 points
- Extra -- 50 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)****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 (Seni-Thue and Thue) and equivalence problems (Thue)****Brief introduction to Post Correspondence Systems and Relation to Semi-Thue Systems**

**Simulating Turing Machine by Semi-Thue System****Simulating Turing Machines by Thue Systems****Grammars and re sets****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)****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 = 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

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

- The Big
Challenge we have is going online for the rest of the
semester.

- 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)
- Midterm Key

**Assignment #5**

Sample with Key

- Unit Execution Time: Trees, forest, anti forests
- UET: DAGs and m=2
- 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
- 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 of K-Color

- I am now requiring that each
of you to develop a paper and a presentation, based on a 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. The
length of the 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 a separate page.
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 must be
designed as if you would be using it to be as part of a
12-minute discussion to your classmates. Note: For shorter
papers you may (likely will) need to investigate some cited
works.

- I have placed over 50 sample papers
out there at SampleTopics. 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. Actually, the one case already
Claimed is from someone who sent the paper my way. Please send
me an email to assure you "claim."

- Realize that many of these
are 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.

This folder contains some examples (papers and presentations) from past semesters.

- Final Exam will need
to be done at home. I need to know that each of you has a web
cam so we can use some of the exam proctoring tools developed
for remote exam taking. If you do not, let me know ASAP.

**Final Paper and PowerPoint**

**Read above****. Its weight is now at least 125 points.**

It goes higher if you attack a challenging topic and do really well on it.

Note that I increased the bonus weight to 50 and allow it on the Paper/Presentation

**Due: 4/23**

**Assignment #6**

Sample with Key

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

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

- EXPSPACE, EXPTIME, NEXPTIME
- ATM (Alternating NDTM)
- QSAT. Petri Nets, Presburger
**Validity of SubsetSum optimization reduction to SubsetSum Decision Problem Oracle**

**2SAT****(linear time complexity)****Uniform Min-1 is NP Equivalent****Propositional Calculus**

**Axiomatizable Fragments**

**Unsolvability for Membership in Fragments of Diadic Partial Implicational Propositional Calculus**

- Finite Convergence

**Finite Power Problem for CFLs**

Revisit Set Real-Time (Constant-Time)

**Real-Time and Mortal Machiness** - 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)

**All Project Papers and Presentations are Due on Wednesday, 4/****23**by midnight- Final Exam will need to be done at home. It will be on Webcourses and you will be on your honor.