| Click for the "scroll" |
| 1. |
Why Study Computability, Complexity, and Languages?
(revised with discusson related to studying complexity theory in the age of deep learning --
September 10, 2019)
|
| 2. |
Sets, Tuples, Cartesian Products, Partial and Total Functions,
Predicates, Quantifiers, Proofs
(scroll corrected August 21, 2017)
|
| |
| PART 1: Computability |
| |
| 3. |
The Minimalist (but all powerful) Programming Language S
(scroll revised August 28, 2013)
|
| 4. |
Partially Computable Functions
(scroll corrected September 11, 2015)
|
| 5. |
Primitive Recursive Functions
(scroll corrected September 20, 2017)
|
| 6. |
Sixteen Building-Block PRC Functions
(scroll revised August 29, 2013)
|
| 7. |
The Pairing Function and The Godel Numbers
(scroll corrected September 11, 2015)
|
| 8. |
Church's Thesis and the Unsolvability of the Halting Problem
|
| 9. |
A Universal Program that can Execute Any Program and the Concept of
Recursive Enumerability
|
| 10. |
Calculations on Strings, and the Minimalist (but all powerful) Language
Sn for String Processing
(scroll revised September 20, 2013)
|
| 11. |
The Post-Turing Language T for String Processing and the Equivalence
of S, Sn, and T
(scroll corrected September 15, 2017)
|
| 12. |
Turing Machines
(scroll corrected September 15, 2017)
|
| 13. |
What's Meant by a Turing Machine Accepting a Language
|
| |
| PART 2: Grammars and Automata |
| |
| 14. |
String Computations with Productions and Processes
|
| 15. |
Post's Correspondence Problem and Grammars
|
| 16. |
Phrase Structure Grammars and Context Sensitive Grammars
(scroll corrected September 20, 2017)
|
| 17. |
Finite Automata and Regular Languages
|
| 18. |
Properties of Regular Languages
(scroll corrected October 7, 2017)
|
| 19. |
Regular Expressions and the Pumping Lemma
(scroll corrected October 7, 2017)
|
| 20. |
Context-Free Languages
(scroll corrected October 23, 2015)
The two scribbles you see at the bottom right of the second page are my mother's signature dating
back to the year 2006 when she visited Lafayette. A woman of indomitable spirit who raised five children
' under difficult circumstances, she passed away in 2012.
|
| 21. |
Regular Grammars, Chomsky Normal Form, and Bar-Hillel's Pumping
Lemma
(scroll revised October 13, 2011)
|
| 22. |
Properties of Context-Free Languages
(scroll corrected October 23, 2015)
|
| 23. |
Bracket Languages and the Pushdown Automata
|
| |
PART 3: The Theory of NP-Completeness
|
| |
| 24. |
Computational Complexity: Some Basic Definitions
|
| 25. |
Defining P and NP
(scroll revised December 16, 2011)
|
| 26. |
A More Formal Definition of Class NP
(scroll updated November 30, 2015)
|
| 27. |
Polynomial Transformability of Problems in Class NP
(scroll revised December 16, 2011)
|
| 28. |
Definition of NP-Complete and the SATISFIABILITY Problem
(scroll revised November 3, 2011)
|
| 29. |
The Six Basic NP-Complete Problems and the NP-Completeness
Proof for 3SAT
|
| 30. |
NP-Completeness Proofs for 3DM, VC, CLIQUE, HC, and PARTITION
(scroll significantly expanded, November 24, 2015)
|
| 31. |
NP-Completeness Proofs by Restriction: Subgraph Isomorphism (SGI),
KNAPSACK, Multiprocessor Scheduling (MS), and Bounded-Degree
Spanning Tree (BDST)
|
| 32. |
NP-Completeness Proofs by Local Replacement: Sequencing within
Intervals (SQUINT), and Partition into Triangles (PIT)
(scroll revised December 1, 2011)
|
| 33. |
NP-Completeness Proofs by Component Design: Minimum Tardiness
Sequencing (MINTARD)
(scroll corrected November 24, 2015)
|
| 34. |
Reasoning About the Complexity of the Subproblems of a Given
NP-Complete Problem (Example: Graph 3-Colorability)
|
| 35. |
Strong-Sense and Weak-Sense NP-Completeness for Number
Problems
(scroll revised December 16, 2011)
|
| 36. |
Extending the Complexity Theory to Search Problems
|
| 37. |
Generalizing Polynomial Transformability to Turing Reducibility
and the Definition of NP-Hard
|
| 38. |
Complements and Optimization Versions of the NP-Complete
Decision Problems
(scroll revised December 15, 2011)
|
| 39. |
Approximation Algorithms for Combinatorial Optimization:
Bin Packing Optimization (BINPACKO), Traveling Salesman
(Restricted) Optimization (TSRO), etc.
|
| 40. |
Nonapproximable and Easily Approximable NP-Hard Optimization
Problems: Graph Coloring Optimization Problem (GRAPHCOLO),
Knapsack Optimization Problem (KNAPSACKO), etc.
(scroll revised December 15, 2011)
|
| 41. |
The Classes NPI, co-NP, PNP and NPNP of Problems and
the Class #P of Enumeration Problems
(scroll corrected December 6, 2017)
|
| 42. |
Storage Considerations: The Classes PSPACE, PSPACE-Complete,
and PSPACE-hard
|
| |
PART 4: Random Graphs
|
| |
| 43. |
Random Graphs: An Introduction
|
| |
| 44. |
The Degree Sequence and Polynomial-Time Graph Isomorphism
for Random Graphs
|
