--------------------------------
01. Time-bounded Turing machines
--------------------------------
- a DTM that finishes in time no more than T(n) -- "n" being the size of the input

---------------------------------
02. Class P of problems/languages
---------------------------------
- when T(n) is a polynomial function of n on a DTM
- examples: 
	+ is w in G for a CFG G?
	+ is there a path from node x to node y in graph G?
	+ the Pseudo-Knapsack problem

----------------------------------
03. Class NP of problems/languages
----------------------------------
- when T(n) is a polynomial function of n on a NTM
- example: the Knapsack problem
- NP completeness

------------------------------
04. Polynomial time reductions
------------------------------
- polytime transducer (-p->)
- used to prove specific problems NP-complete

----------------------------------
05. NP-complete problems/languages
----------------------------------
- Cook's Theorem: SAT is NP-complete (every NTM -p-> SAT)
- CSAT is NP-complete (every NTM -p-> CSAT)
	+ SAT in Conjunctive Normal Form (CNF)
	+ conversion to CNF
- 3-SAT is NP-complete (CSAT -p-> 3-SAT)
- Node cover is NP-complete (3-SAT -p-> Node cover)
- Knapsack is NP-complete (3-SAT -p-> Knapsack /w target -p-> Knapsack)

--------------------
06. NP-hard problems
--------------------
- problems that seem not to be in NP
- Co-NP: the complement is in NP
- example: the Tautology problem is NP-hard