verified in polynomial time. The travelling salesperson problem is definitely one
of these because checking whether a given route is a shorter distance than any
given distance can be done in polynomial time. You just add the distances along
the given route and compare it with the given number. Finding and verifying are
two different operations: for instance, it is easy to verify that 167 × 241 =
40,247 but finding the factors of 40,247 is a different proposition.
Is every problem verifiable in polynomial time able to be solved in polynomial
time? If this were true the two classes P and NP would be identical and we could
write P = NP. Whether P = NP is the burning question of the day for computer
scientists. More than half the profession think this is not true: they believe there
are problems out there that can be checked in polynomial time but cannot be
solved in polynomial time. It is such an outstanding problem that the Clay
Mathematics Institute has offered a prize of $1,000,000 to prove whether P = NP
or P NP.

The condensed idea

Finding the best route