Notices to three friends

This post aims to show a surprising connection between a well-known computer science concept (NP-complete problems) and the reasons for why computers have become so ubiquitous in the modern world. If you’ve never heard of NP-complete problems the “Why computers are special devices” section might still be of interest!

These are often said to be the “hardest problems” in class NP. The class NP is a broader class of search problems where a solution, once found, can be efficiently verified as correct. Consider for example this problem: you’re given a social network and a number K and you need to figure out if there is a group of K people in this network that all know each other. That is an NP-complete problem.

The reason these problems are said to be the hardest in NP is because they have a remarkable property – it has been shown that if you found an efficient algorithm for any of them you could use it to construct efficient algorithms for all problems in NP. This is why they are called “complete“ - they capture every problem in the class while also themselves belonging to it.

It is also why recognising an algorithmic problem as NP-complete is usually taken as a sign that looking for an efficient algorithm to solve it is hopeless and one should instead be looking at heuristics or approximation algorithms.

Leave a Comment