ECE 664

Computability, Complexity, and Languages


Avinash Kak

Fall 2017

Click for the "scroll"
1.   Why Study Computability, Complexity, and Languages?
   (revised with minor changes August 21, 2017)
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
  (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

  (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 revised December 6, 2011)
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

FEEDBACK WELCOME! If you have any comments or any suggestions for improving these notes, please send an email to  with the string  "Comments on ECE 664"   in the subject line to get past my spam filter. Any suggestions that I incorporate would be duly acknowledged.

A NOTE FOR INSTRUCTORS USING THESE "SCROLLS": About the "scrolls" that are handed out in class, they look best when printed in color on long sheets of light yellow paper of size 11 in x 17 in (28 cm x 44 cm). Obviously, this is not the size of paper you can use with a home printer. However, many office copying/printing machines these days can make copies of this size without difficulty.

Valid HTML 4.01 Transitional Valid CSS!