4 ms·
--Edit: this was wrong, see reply comment-- NP: you can verify the answer is correct in polynomial time. (and no other clauses) Anything in P is in NP
by quickthrower2 3y ago
--Edit: this was wrong, see reply comment--
NP: you can verify the answer is correct in polynomial time. (and no other clauses)
Anything in P is in NP
- Dylan16807 3y agoI think it's worth saying what NP stands for. Nondeterministic Polynomial. Where "nondeterministic" basically means you get to try every single polynomial solution in parallel.
- minitech 3y agoNot wrong, just a different criterion that describes the same complexity class.
- raincole 3y ago> --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.