The whole challenge of the "Travelling salesman problem" is to find the simplest (shortest) algorithm to solve the problem. That means the issue is to solve problems. To check the solution and how difficult that is, is no issue.
Chess is a typical example which belongs in the category difficult to solve and difficult to check. The computer can tell you what the best solution is, but to check that you have to execute the algorithms involved. In stead of difficult you can also write efficiently
The question: "what are the two prime numbers that you get when you multiply them and the answer is 143", is a simple question. The difficulty of the problem depends about the size of the prime numbers involved. With difficulty I mean (computer) time to find the solution and not so much the complexity of the calculations involved.
If I tell you that one answer is 11 than the problem becomes easier to solve and to find the second number i.e. 13. I specific write here to solve want in fact if I give you part of the answer (i.e. help) I have modified the original problem.
In short IMO this whole topic (to solve versus to check) is rather irrelevant.
Back to my home page Index