4 ms·
> [...] which is true for any problem that's not hard hard. Yes, basically true for any problem where you can verify a correct answer in polynomial time (espec
by eru 2y ago
> [...] which is true for any problem that's not hard hard.
Yes, basically true for any problem where you can verify a correct answer in polynomial time (especially if someone gives you extra hints to help your verification).
You can also think of these 'hints' as 'extremely lucky guesses'.
Eg you can verify that a number is composite, and not prime, by 'guessing' its prime factors.
Or you can guess the solution to a Sudoku and then just verify it.
The traveling salesman problem is interesting: it's trivial to verify that any given candidate solution has a specific cost (and that cost can be very low), but it's not trivial to verify that the candidate is minimal. (I'm not even sure it's possible in polynomial time.)