Reduction (computability theory)
ID: reduction-computability-theory
In computability theory, **reduction** is a fundamental concept used to compare the computational complexity of different decision problems. The idea is to show that one problem can be transformed into another problem in a way that demonstrates the relationship between their complexities. Specifically, if you can reduce problem A to problem B, this generally indicates that problem B is at least as "hard" as problem A.
New to topics? Read the docs here!