Could you please suggest some examples of problems with answers that are easy to verify…
- User
Could you please suggest some examples of problems with answers that are easy to verify but hard to find? A typical example would be prime factorisation, but problems that are easier to demonstrate to an audience without a strong mathematical background would be preferable. Bonus points if it doesn't involve arithmetic.
Assistant
One classic example of a problem that is easy to verify but hard to find is the Traveling Salesman Problem (TSP). Here's an explanation that doesn't heavily rely on math jargon:
Imagine a salesperson needs to visit a number of cities (let's say 10 cities), and the goal is to find the shortest possible route that visits each city exactly once and returns to the starting city. Given a map with the distances between each pair of cities, it's straightforward for anyone to check if a proposed route is indeed the shortest one: just add up the distances and compare it with other routes. However, finding the absolute shortest route can be incredibly difficult as the number of cities increases.
Another example is the coloring problem: Given a map with regions (states, countries, or any other areas), you want to color the map using the minimum number of colors such that no two adjacent regions have the same color. Verifying if a coloring is correct is simple — just look if any neighboring regions share a color. But finding the optimal coloring (using the fewest colors possible) can be quite challenging, especially as the map gets more complex.
A more visual example is the汉诺塔(Hanoi Tower) puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
- No disk may be placed on top of a smaller disk.
It's easy for anyone to check if a sequence of moves is valid (if it follows the rules), but finding the minimum number of moves to solve the puzzle with a large number of disks is not直观(intuitive) and can be quite challenging.
These examples demonstrate problems where the solution's correctness is simple to verify, but finding the solution itself can be computationally complex or require clever problem-solving strategies.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.