Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.04308 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908633243058176 |
|---|---|
| author | Grüne, Christoph Pfaue, Femke |
| author_facet | Grüne, Christoph Pfaue, Femke |
| contents | The website reductions.network serves as a comprehensive database for exploring problems and reductions between them. It presents several complexity classes in the form of an interconnected graph where problems are represented as vertices, while edges represent reductions between them. This graphical perspective allows for identifying problem clusters and simplifying finding problem candidates to reduce from. Moreover, users can easily search for existing problems via a dedicated search bar, and various filters allow them to focus on specific subgraphs of interest. The design of the website enables users to contribute by adding new problems and reductions to the database. Furthermore, the software architecture allows for the integration of additional graphs corresponding to new complexity classes. In the current state, the following networks with their respective complexity classes are included:
- classical complexity including the classes NP, #P, and SSP-NP
- parameterized complexity including the classes W[1], W[2]
- gap-preserving reductions under the PCP-Theorem and the Unique Games Conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_04308 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Compendium of Reductions: reductions.network Grüne, Christoph Pfaue, Femke Computational Complexity The website reductions.network serves as a comprehensive database for exploring problems and reductions between them. It presents several complexity classes in the form of an interconnected graph where problems are represented as vertices, while edges represent reductions between them. This graphical perspective allows for identifying problem clusters and simplifying finding problem candidates to reduce from. Moreover, users can easily search for existing problems via a dedicated search bar, and various filters allow them to focus on specific subgraphs of interest. The design of the website enables users to contribute by adding new problems and reductions to the database. Furthermore, the software architecture allows for the integration of additional graphs corresponding to new complexity classes. In the current state, the following networks with their respective complexity classes are included: - classical complexity including the classes NP, #P, and SSP-NP - parameterized complexity including the classes W[1], W[2] - gap-preserving reductions under the PCP-Theorem and the Unique Games Conjecture. |
| title | A Compendium of Reductions: reductions.network |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.04308 |