Every problem Y in NP is accepted by some nondeterministic machine N with polynomial running time p(n), and the map x ↦ ⟨⌈N⌉, x, 1^p(|x|)⟩ is a polynomial-time reduction of Y to BHP
Nondeterministic machine(in computer science and computational theory)
A theoretical computer that can explore multiple possible paths of calculation at the same time, unlike real computers that follow one step at a time.
Polynomial running time(describing how fast an algorithm executes)
A computational time that grows at a reasonable rate relative to the size of the input (for instance, doubling the input doesn't make it take astronomically longer).
Reduction (polynomial-time reduction)(as used in computational complexity)
A way to transform one difficult problem into another difficult problem using a fast method, proving that if you can solve one quickly, you can solve the other quickly too.
The map x ↦ notation(as used in mathematical notation)
Mathematical shorthand meaning 'take an input x and transform it into this new form'—the arrow shows what transformation happens.
Similarly, parts i) and ii) respectively implies that \(\textbf{P} \subsetneq \textbf{EXP}\) and \(\textbf{NP} \subsetneq \textbf{NEXP}\). And it similarly follows from part iii) that \(\textbf{L} \subsetneq \textbf{PSPACE}\). Note that since every deterministic Turing machine is, by definition, a non-deterministic machine, we clearly have \(\textbf{P} \subseteq \textbf{NP}\) and \(\textbf{PSPACE} \subseteq \textbf{NPSPACE}\). 2 Suppose that \(f(n)\) is both time and space constructible. Then