This content has been automatically translated from Ukrainian.
NP-completeness is a class of problems for which it is very difficult to find a solution, but easy to verify the correctness of an already found one. In other words, if you guess the answer, you can check it quickly, but the actual search process takes an extraordinarily long time.
Examples of NP-complete problems:
- Traveling salesman problem - how to find the shortest route that visits all cities.
- Timetable scheduling - to create an optimal schedule so that all teachers, classrooms, and students coincide without conflicts.
- Subset sum problem - to divide a set of numbers into groups with the same sum.
Where this is important in real life:
- Logistics and delivery routes.
- Production planning and schedules.
- Cryptography and data security.
A simple Ruby example to demonstrate the idea of brute force (using subsets):
# NP-complete problem: finding a subset with the desired sum
numbers = [3, 7, 9, 11, 15]
target = 20
solutions = []
(1..numbers.size).each do |k|
numbers.combination(k).each do |subset|
solutions << subset if subset.sum == target
end
end
puts "Found solutions:"
solutions.each { |s| p s }
Result:
Found solutions: [9, 11]
Here we can see several options at once. And if we increase the array to 20–25 numbers, the number of checks will increase sharply - this is what combinatorial explosion looks like, which is why such NP-complete problems become practically unsolvable through brute force.
