Theory Key Concepts

NFA and DFA

• Proving regularity
• Number of Equivalence Classes
  • <math>u,\; v</math> are equivalent iff for any <math>w</math>, <math>uw\;\in\;L\; \Leftrightarrow\; vw\;\in L</math>.
• Pumping Lemma

Proving NP-completeness

• A < B implies that if we could solve B we could solve A. Which means that we can write a algorithm to solve A which calls the algorithm for solving B in the process. Any additional operations in A must be polynomial in time.

• 3-Sat < Graph-3 Coloring : count=0
• Graph-3 Coloring < 3-Sat : count=1
• Clique
• Vertex Cover : count=1
• Independent Set : count=1
• Subset Sum
• Max Cut

Halting Problem

• RE and Co-RE
• Decideability

Graph Theory

• Minimum Spanning Tree
• Max Flow
• Min Cut
• Single Pair Shortest Path
• All Pairs Shortest Path