You need to enable Java-Script to run this page.

Reductions Network<br>- A Compendium of Reductions -

This website provides graphs of reductions between problems of several complexity classes.<br>The vertices represent the problems and the edges represent the reductions.<br>By clicking on the vertices or edges you are able to access additional information.<br>We are interested in extending the database in terms of complexity classes, reductions and problems.<br>If you want to add a reduction or problem to a network, please go to the network and click on the -button.

The Reduction Networks

NP and #P-->

[parsimonious]

[SSP]

Parameterized Complexity -->

[FPT]

Complexity of Approximation -->

[PCP-Theorem]

[Unique Games Conjecture]

Citing the Reductions Network Compendium Website

Please use the following BibTeX entry if you want to cite our website.<br>Please also remember to additionally cite the original work.

@misc{ReductionsNetwork,<br>title={A Compendium of Reductions: reductions.network},<br>author={Christoph Grüne and Femke Pfaue},<br>year={2025},<br>eprint={2511.04308},<br>archivePrefix={arXiv},<br>url={https://arxiv.org/abs/2511.04308},<br>note = {\url{https://reductions.network}},

Reduction of the Day