For instance, the following is often described as the single most important open question in all of theoretical computer science: Open Question 1 Is \(\textbf{P}\) properly contained in \(\textbf{NP}\)? 1. 3 Reductions and \(\textbf{NP}\)-completeness Having now introduced some of the major classes studied in complexity theory, we next turn to the question of their internal structure. This can be studied using the notions of the reducibility of one problem to another and of a problem being comp