Universality Leads to NP-Complete Problems

There is a surprising link between universality and NP-complete problems in computer science.

Important context: finding an algorithm to solve an NP-complete problem would mean solving all problems of the same class.

Computation can be thought of as the solution to the NP-complete problem of executing computable functions. A function can be computed on any machine with the same set of inputs, a sequence of instructions, for any computable problem (e.g. you don’t need to buy a special machine to run Slack).

When we talk about NP-complete problems we typically talk about specific classes that have resource constraints. For instance, there are many classes of complete problem with respect to time—they are computable but would take many years to complete (e.g. breaking 256-bit encryption would take millions of years).

Universality explains why NP-complete problems exist because they are a subset of what’s solvable by a universal computation machine. We know this because resource constraints can be simulated in a universal computing machine by measuring resources and stopping execution if the constraint is exceeded.

Memory usage, CPU usage, time are constraints that are important to making solutions practical, not to make them solvable altogether. In fact, it’s because it is solvable (due to universality) that NP-complete problems exist at all.

Read Why are there complete problems, really?