Practice question · Multiple choice
A problem is shown to be NP-complete. Why is that useful news rather than merely bad news?
Hints
- Ask what a team would do differently on Monday knowing the problem is NP-complete.
- Travelling salesman instances with thousands of cities are solved daily. What does that tell you?
Show the answer
B. Because it redirects the effort toward approximation or heuristics
Why
It tells you which search to abandon. Real instances are routinely solved by approximation, branch-and-bound, or exploiting structure the general problem lacks, so the classification redirects rather than closes the work, and knowing it early saves months of looking for something almost certainly not there.
Practise Integrated Algorithm Design Practice
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Integrated Algorithm Design Practice
- For 'find the k most frequent words in a huge text', select every design decision the lesson endorses.
- Given a new problem, an experienced programmer often recognises it as a variant of something known - shortest…
- The fastest algorithm for a problem in the abstract is the right choice regardless of the data and…
- Order the first five steps of the design workflow the lesson recommends.
- Match each data structure to the hot operation it makes fast.