Computability and Complexity

Table of Contents

This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is Computer Science and Math students with some background in programming, data structures, and discrete math, such as a sophomore in a Computer Science program.

• Introduction
• Formal Languages
  • Chomsky Hierarchy
    • Regular Languages - sample DFA inputs
    • Context Free Languages - sample PDA inputs
    • Context Sensitive Languages - sample LBA inputs
    • Unrestricted Languages - sample TM inputs
  • Other Language Classes
    • Counting Languages - sample CA inputs
• Computability
  • Decidability
  • Reducibility
• Complexity
  • Time Complexity
    • P
    • P-Complete
    • NP
    • NP-Complete
  • Space Complexity
    • L
    • NL
    • NL-Complete
    • PSPACE
    • PSPACE-Complete
• References and Further Reading