Imagen de Portada

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Pfaue, Femke
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Compendium of Reductions: reductions.network
por: Grüne, Christoph, et al.
Publicado: (2025)

BusOut is NP-complete
por: Ishibashi, Takehiro, et al.
Publicado: (2025)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
por: Bartlett, Celina Janet
Publicado: (2025)

Reductions Between Code Equivalence Problems
por: Cheraghchi, Mahdi, et al.
Publicado: (2025)

The 2-Attractor Problem is NP-Complete
por: Fuchs, Janosch, et al.
Publicado: (2023)

Limit-sure reachability for small memory policies in POMDPs is NP-complete
por: Asadi, Ali, et al.
Publicado: (2024)

Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
por: Binnendyk, Eric
Publicado: (2025)

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
por: Zhan, Junpeng
Publicado: (2023)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
por: Guruswami, Venkatesan, et al.
Publicado: (2023)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
por: Istrate, Gabriel
Publicado: (2024)

Limits of structures and Total NP Search Problems
por: Ježil, Ondřej
Publicado: (2023)

Information Redistribution Under Reductions in NP Search
por: Wei, Jing-Yuan
Publicado: (2026)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
por: Digulescu, Mircea-Adrian
Publicado: (2026)

King Chasing Problem in Chinese Chess is NP-hard
por: Li, Chao, et al.
Publicado: (2026)

Gap Preserving Reductions Between Reconfiguration Problems
por: Ohsaka, Naoto
Publicado: (2022)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
por: Chavrimootoo, Michael C.
Publicado: (2024)

NP-Hardness and a PTAS for the Pinwheel Problem
por: Kleinberg, Robert, et al.
Publicado: (2026)

P=NP
por: Deng, Zikang
Publicado: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
por: Chavrimootoo, Michael C., et al.
Publicado: (2026)

Wataridori is NP-Complete
por: Ruangwises, Suthee
Publicado: (2026)

P vs. NP
por: Uribe, Daniel
Publicado: (2016)

On P Versus NP
por: Gordeev, Lev
Publicado: (2020)

Nondango is NP-Complete
por: Ruangwises, Suthee
Publicado: (2023)

The n-vehicle exploration problem is NP-complete
por: Cui, Jinchuan, et al.
Publicado: (2023)

Evolomino is NP-complete
por: Nikolaev, Andrei V.
Publicado: (2025)

Proofs of NP = coNP = PSPACE: Current upgrade
por: Gordeev, Lev, et al.
Publicado: (2023)

On $NP \cap coNP$ proof complexity generators
por: Krajicek, Jan
Publicado: (2025)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
por: DeJesse, Nicholas, et al.
Publicado: (2025)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
por: Yang, Chao, et al.
Publicado: (2024)

Communication Complexity is NP-hard
por: Hirahara, Shuichi, et al.
Publicado: (2025)

On Kernelization with Access to NP-Oracles
por: Molter, Hendrik, et al.
Publicado: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
por: Nederlof, Jesper
Publicado: (2026)

There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$
por: Kayibi, Koko-Kalambay Kalafan
Publicado: (2018)

NP-Completeness of Neighborhood Balanced Colorings
por: Asaeedi, Saeed
Publicado: (2024)

A Critique of Deng's "P=NP"
por: Humphreys, Isabel, et al.
Publicado: (2025)

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
por: Arvind, Vikraman, et al.
Publicado: (2024)

NP-Completeness of Multicast Beamforming in Wireless Communication
por: Shrestha, Sagar
Publicado: (2025)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
por: Johnson, Matthew, et al.
Publicado: (2022)

Some conditions implying if P=NP then P=PSPACE
por: Rodriguez, Ismael
Publicado: (2026)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
por: Mitosek, Piotr
Publicado: (2024)