---

email: charles.e.hughes@knights.ucf.edu

---

Structure: TR 1330-1445 (1:30PM-2:45PM); ENGR1-286; 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; 823-2762
Office Hours: TR 3:15PM-4:30PM

Office Hours: Tentatively MW 3:15PM-4:30PM

Required Reading: Notes (PowerPoint Version)

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.
• 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/~odedg/cc-drafts.html
• Arora&Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  Draft available at http://www.cs.princeton.edu/theory/complexity/
• 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/~odedg/bc-drafts.html
• Sipser, Introduction to the Theory of Computation 3rd Ed., Cengage Learning, 2013.

Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cot6410/Spring2015
Notes URL: http://www.cs.ucf.edu/courses/cot6410/Spring2015/Notes/COT6410NotesSpring2015.pdf
http://www.cs.ucf.edu/courses/cot6410/Spring2015/Notes/COT6410NotesSpring2015.pptx

Assignments: Around 6 to 10; Paper + Presentation

Exams: midterm and a final.

Exam Dates (Tentative): Exam#1 – Tuesday, March 3; Spring Break – March 9-14; Withdraw Deadline – Tuesday, March 24; Final – Tues., May 5, 1:00PM–3:50PM

Evaluation (Tentative):

1. Mid Term – 125 points; Final Exam – 175 points (balance between weights will be adjusted in your favor)
2. Assignments – 100 points; Paper and Presentation – 75 points
3. Extra -- 25 points used to increase weight of exams or assignments, 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

.

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. Basic notions of computability and complexity
8. Existence of unsolvable problems (counting and diagonalization)
9. Solved, solvable (decidable, recursive), unsolved, unsolvable, re, non-re
10. Hilbert's Tenth
11. Undecidable problems made a bit more concrete
    
12. Lots about problems and their complexity
13. Halting Problem (HALT) is re, not decidable
14. Set of algorithms (TOT) is non-re
    
15. Halting Problem seen as fun
    

Assignment #1

Review of some closure properties of formal languages
Word Version

Due: 2/5 (Key)

1. Some consequences of non-re nature of algorithms
   
2. 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 compuation 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
3. Systems related to FRS (Petri Nets, Vector Addition, Abelian Semi-Groups)
4. RM simulated by Ordered FRS
5. Primitive Recursive Functions (prf)
6. Initial functions
7. Closure under composition and recursion

Assignment #2

Closure properties of recursive, re and non-re sets
Word Version

Due: 2/3 (Key)

1. Primitive Recursive Function in detail
2. Addition and multiplication examples
3. Sample functions and predicates
4. Closure under cases
5. Bounded minimization
6. Arithmetic fuctions that use bounded search
7. Pairing functions
8. Limitations of primitive recursive
9. mu-recursion and the partial recursive functions
10. Notions of instantaneous descriptions
11. Encodings
12. Equivalence of models
13. TMs to Register Machines
14. RM to Factor Replacement Systems
15. Factor Replacement to Recursive Functions
16. Gory details on FRS to REC
    
17. Universal machines
18. Recursive Functions to TMs
    
19. Consequences of equivalence

1. Primitive recursive functions SNAP, TERM, STP and VALUE
2. Review Undecidability (Halting Problem, shown by diagonalization)
3. RE sets and semidecidability
4. The set of all re sets W₀, W₁, W₂, ...
5. Enumeration Theorem
6. The set K = { n | n is in the n-th re set } = { n | n is in W_n } is re, non-recursive
7. The set K₀ = HALT = { <n,x> | x is in the n-th re set }
8. Alternative characterizations of re sets
9. Parameter Theorem (aka Sm,n Thearem)
10. Quantification and re sets
11. Quantification and non-re sets
12. Diagonalization revisited (set of algorithms is non-re and K₀ (Lu) = HALT is non-rec)

Assignment #3 (not graded)

Closure of primitive recursive functions under halfway and halfway mutual induction
Word Version

1. Reduction
2. Classic sets Ko (Lu), NON-EMPTY (Lne), EMPTY (Le)
3. Reduction from Ko that shows undecidability of K, HasZero, IsNonEmpty, HasIndentity, TOTAL, IsZero, IsEmpty, IsIdentity
   
4. Equivalence of certain re sets (K, HasZero, IsNonEmpty, HasIndentity) to Ko
5. Equivalence of centain non-re sets (IsZero, IsEmpty, IsIdentity) to TOTAL
   
6. Reducibility and degrees (many-one, one-one, Turing)
7. Complete re set (K and K₀ as examples)
8. Note: To be re-complete a set must be re
9. Hierarchy or RE equivalence class (m-1 and 1-1 degrees)
   
10. Rice's Theorem
11. "Picture" proofs for Rice's Theorem
12. Constant Time and Mortal Machines
13. END OF MATERIAL FOR Midterm

Assignment #4

Quantification approximations of Complexity
Word Version

Due: 2/24 (Key)

1. Introduction to rewriting systems (Thue, Post)
2. Semi-Thue systems
3. Word problems
4. Simulating Turing Machine by Semi-Thue System
5. Simulating by Thue Systems
6. Post Canonical Forms
7. Post Correspondence Problem
8. Grammars and re sets
9. Unsolvable problems related to context-free grammars/languages
10. Ambiguity of CFGs
11. Non-Emptiness of CFL Intersections

    Assignment #5


Quantification, Reduction and Rice's Theorem
Word Version

    Due: 2/26 (Key)

1. Sample Midterm (Word Version)
2. Review and go over sample questions
3. Sample Midterm Key (Word Version)
4. Key for Samples from Notes (PowerPoint Version)
5. Context-Sensitive Grammars and Unsolvability Results
6. Valid (CSL) and Invalid Traces (CFL)
7. Intersection and Quotients of CFLs
8. Details on Valid (CSL) and Invalid Traces (CFL)
9. Intersection of CFLs revisited
10. Quotients of CFLs revisited
11. Type 0 grammars and Traces
12. L =  S*  for L a Regular or CFL
13. L=L^2 for L a CFL

1. HELP SESSION on Monday, March 2, from 10:00 to 11:20 in ENGR1-383
   
2. More practice problems (Spring 2014 midterm and key)
   
3. Midterm (Tuesday)
4. Summary of Grammar Results
   
5. Finite Convergence
6. Revisit Set Real-Time (Constant-Time)
7. Real-Time and Mortal Machines
8. Finite Power Problem for CFLs
9. L =  S*  for L a Regular or CFL
   
10. Propositional Calculus
11. Axiomatizable Fragments
12. Unsolvability for Membership in Fragments of Diadic Partial Implicational Calculus
13. Fast Review of Order Analysis (not in class but on your own)
    

Week#9: SPRING BREAK

Week#10: (3/17, 3/19) -- Notes pp. 304-320 (Briefly Again); 328-438

1. Review of Undecidability of Derivability Problem for Finitely Axiomatizable Fragments of Proposition Calculus
   
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. 3SAT <=_P SubsetSum
18. SubsetSum <=_P Partition
19. Partition equivalence to SubsetSum
20. Key to Midterm

 Presentation Stage #1

                Turn in a list of team members (2 preferred but 3 okay)
                Turn in a citation to paper(s) being proposed as basis for paper and Presentation
                 Paper being read should have length equivalent to 8 or more single-spaced, two-column journal pages
                    Must be at least 12 pages if three members in group (two 6- to 8-page papers works as well)
                 Your paper that summarizes and highlights must be at least 6 pages, double-spaced, single column
                    Must be at least 8 pages if three members in group

                 Sample Topics

  Assignment #6 

        Reductions from SAT

1. Note: 3/24 is the Withdraw Deadline
2. Knapsack (relation to SubsetSum), Dynamic Programming Approach
3. Bin packing (fixed capacity, minimize number of bins)
4. Pseudo polynomial-time solution for Knapsack using dynamic programming with changed parameters, n*W versus 2^n
5. Reduction techniques
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 first fit, greedy best fit,  sorted, optimalGreedy versus optimal (N/(N+1))
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

        Assignment #7

             Scheduling Problems

1. Hamiltonian Path
2. Travelling Salesman
3. Integer Linear Programming
4. Tiling the plane and Bounded Tiling
5. Bounded PCP
   
6. co-NP
7. P = co-P ; P contained in intersection of NP and co-NP
8. NP-Hard
9. QSAT as an example of NP-Hard, possibly not NP
10. NP-Hard problems are in general functional not necessarily decision problems
11. NP-Complete are decision problems as they are in NP

1. You must send me preferred day of presentation by 4/7 at 6:00PM.
   
• The days to choose from are 4/14, 4/16, 4/21, 4/23.
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)
• The abstract must include title and team member names
• It is designed so everyone is mentally prepared for your presentation
  
3. All papers and final versions of presentation slides are due as pdf files by 11:59 on 5/1
• 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
4. Clean-up (PSPACE, FP, FNP, TFNP, NP-Easy, NP-Equivalent)
5. NP contained in PSPACE
6. FP is functional equivalent to P; R(x,y) in FP if can provide value y for input x via deterministic polynomial time algorithm
7. FNP is functional equivalent to NP; R(x,y) in FNP if can verify any pair (x,y) via deterministic polynomial time algorithm
8. 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)
  
9. Factoring is in TFNP, but is it in FP?
   
• If TFNP in FP then TFNP = FP
10. P = (NP intersect Co-NP) is interesting analogue to intersection of RE and co-RE but may not hold here
11. 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)
12. NP-Easy -- these are problems that are polynomial when using an NP oracle
13. 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
  
14. More NP-Complete poroblems (fun ones)
15. Review based on Midterm Exam (Key to Midterm)

1. Presentation Day 1 (2 presentations)
• 1:30-1:55
  Sarfaraz Hussain, Salman Khokhar, Khurram Soomro
  Ladicky, L'ubor; et al. (2014). Associative hierarchical random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence 36(6): 1056-1077.
• 1:55-2:15
  Navid  Kardan, Ardalan Naseri
  Cabessa, Jérémie; Siegelmann, Hava T. (2012). The computational power of interactive recurrent neural networks. Neural Comput. 24(4), 996-1019.
  
2. 2:15-2:45
   Final Exam Topics
   Start Review of Complexity Material
   
3. Presentation Day 2 (4 presentations)
• 1:30-1:50
  Charly Collins, Rachel Phillips
  Traversa, Fabio L.; Ramella, Chiara; Bonani, Fabrizio; Di Ventra, Massimiliano (2014). Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states, Cornell University Library arXiv:1411.4798v2 [cs.ET]
  
• 1:50-2:10
  Ramin Izadpanah, Rahmatizadeh Rouhollah
  Doty, D., Kari, L., & Masson, B. (2013). Negative interactions in irreversible self-assembly. Algorithmica 66(1), 153-172
• 2:10-2:30
  Guillermo Gomez, Lisa Soros
  Collins, P. and van Schuppen, J. H. (2004). Observability of Hybrid Systems and Turing Machines. In Proc. of the 43rd IEEE Conference on Decision and Control, 7-12.
  
• 2:30-2:50
  Shahidul Islam, Min Wang
  Leyton-Brown, Kevin; Hoos, Holger H.; Hutter, Frank; Xu, Lin (2014). Understanding the Empirical Hardness of NP-Complete Problems, Commun. ACM 57(5), 98-107.
4. NP Completeness of Independent Set Problem
   
5. Sample Final Exam (Key)
   

Week#15: (4/21, 4/23)

1. Presentation Day 3 (3 presentations)
• 1:30-1:50
  Sergiu 'Michael' Veazanchin
  Jones, N. D., & Skyum, S. (1977). Complexity of some problems concerning L systems. In Automata, Languages and Programming (pp. 301-308). Springer Berlin Heidelber
• 1:50-2:10
  John Singleton, Toby Tobkin
  Doty, D. (2012). Theory of algorithmic self-assembly. Communications of the ACM 55(12), 78-88.
• 2:10-2:35
  Joshua Burbridge, Wentao Ding, Samer Iskander
  Gonthier, G. (2008). Formal proof–the four-color theorem. Notices of the AMS 55(11), 1382-1393
2. 2:35-2:45
   Continue Complexity Review
   
3. Presentation Day 4 (2 presentations)
• 1:30-1:50
  Yevgeniy 'Gene' Sher
  Nordin, Peter, and Wolfgang Banzhaf. Genetic reasoning evolving proofs with genetic search. Univ., Systems Analysis Research Group, 1996.
• 1:50-2:10
  Amir Emad Marvasti, Ehsan Emad Marvasti
  Assari, S., Zamir, A., & Shah, M (2014). Video Classification using Semantic Concept Co-occurrences. Proceedings of CVPR
  
4. More Review for Final Exam

Week#16:  (4/27 -- Review Day in ENG1-383 from 10:00 to 11:50)

1. Complete Review (Monday, 4/27, ENGR1-383, 10:00-11:50)
   
2. Midterm Helper (Tuesday, 4/28, HEC-101B, 10:30-12:00)
   
3. Due on Friday, 5/1, by midnight
• Paper associated with presentation
• Presentation (pptx, pdf, or whatever)
• Note: pdf files should be accompanied by zip of source