recall

← recall

NP-complete term

hardest problems in NP — no known polynomial algorithm

Traveling salesman, SAT, graph coloring. Practically: when you spot one, stop trying to solve exactly and reach for approximation/heuristics. 'It's NP-complete' is shorthand for 'we won't be solving this fast.'

topics: computer-science, complexity

references: