We know that P is a strict subset of EXP. The class NP lies between them

We discuss the concept of reduction to compare the difficulty of two problems

Then we define NP-hard and NP-complete and state that although NP-complete problems are not easy to solve, because they can be reduced to SAT, they can be solved with SAT solvers.

Other classes

• PSPACE: Taking polinomial space
• LOGSPACE: Taking logarithmic space
• co-NP
• PH
• BPP
• BQP

Theorem

$LOGSPACE\subseteq P\subseteq NP,coNP\subseteq PH\subseteq PSPACE$