> --Edit: this was wrong, see reply comment-- You're not wrong tho. NP problems can be verified in polynomial time. Nondetermisitic turnig machine is like a t

> --Edit: this was wrong, see reply comment-- You're not wrong tho. NP problems can be verified in polynomial time. Nondetermisitic turnig machine is like a turing machine that has multiple "next steps" instead of one at a given time, and can migically choose the correct next step. You can think it as "taking all the possible paths at the same time (but at the end only the correct one matters)". But you can also think it as "given all the 'choices' it made, check if there is actually such a path", in other words, verifying a certification.