Reductions Network
- A Compendium of Reductions -

This website provides graphs of reductions between problems of several complexity classes. The vertices represent the problems and the edges represent the reductions. By clicking on the vertices or edges you are able to access additional information. We are interested in extending the database in terms of complexity classes, reductions and problems. 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 (Nondeterministic Polynomial Time)

  • [parsimonious]
  • [SSP]
NP Network NP Network

W[t] (Fixed-Parameter Hierarchy)

  • [FPT]
W[t] Network W[t] Network

Citing the Reductions Network Compendium Website

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

                
  @misc{ReductionsNetwork,
      title = { {reductions.network}:
          A Compendium of Reductions for various Complexity Classes },
      note = {\url{https://reductions.network}},
      year = {2024},
  }

Reduction of the Day