Since the mid-1970s a major focus of research in complexity theory has been the study of problems which are complete for the class \(\textbf{NP}\) – i.e. so-called NP-complete problems. A canonical example of such a problem is a time-bounded variant of the Halting Problem for \(\mathfrak{N}\) (whose unbounded deterministic version is also the canonical Turing- and many-one complete problem in computability theory):