Computational Complexity Theory
Concerns:
Computationally hard and easy problems, P vs NP. Is P = NP?
Classifying problems according to their complexity
Rigorous proof that a NP problem is NP indeed
Last updated 4 years ago