ProblemReductions is a package for the reduction (or transformation) between computational hard problems. Although the reduction is a common concept in the field of computational complexity, every textbook on this topic defines its own set of problems and reduction rules. Unfortunately, these rules are not directly accessible to the public, especially for people in fields such as quantum many-body physics and statistical physics. This package aims to collect a set of well-known problems and their reductions in one place, and provide a unified interface to access them. We hope this will lower the barrier for researchers to enter this fascinating field.
This package is supported by the open source promotion plan (OSPP) 2024: A Julia package for problem reduction between computational hard problems.
ProblemReductions is a
pkg> add ProblemReductionsTo update, just type up in the package mode.
Just open an issue if you encounter any problems, or have any feature request.