AS others have pointed out, this glosses over the distinction between the decision version of the problem and the optimization version. But the reason that it o

AS others have pointed out, this glosses over the distinction between the decision version of the problem and the optimization version. But the reason that it often gets glossed over is that it doesn't make much of a difference when it comes to the complexity class of the problem. In this case, the decision version of the problem is: Does a path exist shorter than K? But once you have a solution to that, you can use binary search to answer the optimization version of the problem: Find k such that there exists a path = k and no path < k. But when it comes to the question of verifiers the distinction does matter. because NP is only concerned with decision problems the OP is incorrect when he says that there's no poly time verifier, because there is one for the decision version of the problem, and that's all that matters.