Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.15002 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Similar Items
BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)
by: Ishibashi, Takehiro, et al.
Published: (2025)
Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
by: Çivril, Ali
Published: (2021)
by: Çivril, Ali
Published: (2021)
Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)
by: Silva, Lucas de Oliveira, et al.
Published: (2025)
Limit-sure reachability for small memory policies in POMDPs is NP-complete
by: Asadi, Ali, et al.
Published: (2024)
by: Asadi, Ali, et al.
Published: (2024)
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)
by: Johnson, Matthew, et al.
Published: (2022)
Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)
by: Lee, Pin-Hsian, et al.
Published: (2026)
Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
by: Pfaue, Femke
Published: (2024)
by: Pfaue, Femke
Published: (2024)
Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)
by: Nikolaev, Andrei V.
Published: (2025)
The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)
by: Cui, Jinchuan, et al.
Published: (2023)
P=NP
by: Deng, Zikang
Published: (2024)
by: Deng, Zikang
Published: (2024)
The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)
by: Fuchs, Janosch, et al.
Published: (2023)
On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)
by: Krajicek, Jan
Published: (2025)
Reducibility among NP-Hard graph problems and boundary classes
by: Hassan, Syed Mujtaba, et al.
Published: (2024)
by: Hassan, Syed Mujtaba, et al.
Published: (2024)
Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)
by: Gordeev, Lev, et al.
Published: (2023)
Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)
by: Ruangwises, Suthee
Published: (2026)
P vs. NP
by: Uribe, Daniel
Published: (2016)
by: Uribe, Daniel
Published: (2016)
On P Versus NP
by: Gordeev, Lev
Published: (2020)
by: Gordeev, Lev
Published: (2020)
Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)
by: Ruangwises, Suthee
Published: (2023)
Representing Matroids over the Reals is $\exists \mathbb R$-complete
by: Kim, Eun Jung, et al.
Published: (2023)
by: Kim, Eun Jung, et al.
Published: (2023)
A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
by: DeJesse, Nicholas, et al.
Published: (2025)
by: DeJesse, Nicholas, et al.
Published: (2025)
Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
by: Zhan, Junpeng
Published: (2023)
by: Zhan, Junpeng
Published: (2023)
The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)
by: Ahn, Jungho, et al.
Published: (2022)
Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)
by: Hirahara, Shuichi, et al.
Published: (2025)
On Kernelization with Access to NP-Oracles
by: Molter, Hendrik, et al.
Published: (2025)
by: Molter, Hendrik, et al.
Published: (2025)
On the NP-Hardness Approximation Curve for Max-2Lin(2)
by: Martinsson, Björn
Published: (2024)
by: Martinsson, Björn
Published: (2024)
NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
by: Yang, Chao, et al.
Published: (2024)
by: Yang, Chao, et al.
Published: (2024)
A Critique of Deng's "P=NP"
by: Humphreys, Isabel, et al.
Published: (2025)
by: Humphreys, Isabel, et al.
Published: (2025)
NP-Completeness of Neighborhood Balanced Colorings
by: Asaeedi, Saeed
Published: (2024)
by: Asaeedi, Saeed
Published: (2024)
Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)
by: Bergougnoux, Benjamin, et al.
Published: (2025)
NP-Completeness of Multicast Beamforming in Wireless Communication
by: Shrestha, Sagar
Published: (2025)
by: Shrestha, Sagar
Published: (2025)
Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)
by: Ilmavirta, Joonas, et al.
Published: (2023)
Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
by: Mitosek, Piotr
Published: (2024)
by: Mitosek, Piotr
Published: (2024)
The Identity Problem in the special affine group of $\mathbb{Z}^2$
by: Dong, Ruiwen
Published: (2023)
by: Dong, Ruiwen
Published: (2023)
Some conditions implying if P=NP then P=PSPACE
by: Rodriguez, Ismael
Published: (2026)
by: Rodriguez, Ismael
Published: (2026)
The 7 faces of quantum NP
by: Gharibian, Sevag
Published: (2023)
by: Gharibian, Sevag
Published: (2023)
Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
by: Dorfer, Joseph
Published: (2026)
by: Dorfer, Joseph
Published: (2026)
Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
by: Romão, Leonardo Gasparini, et al.
Published: (2025)
by: Romão, Leonardo Gasparini, et al.
Published: (2025)
The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
by: Meng, Boning, et al.
Published: (2025)
by: Meng, Boning, et al.
Published: (2025)
Limits of structures and Total NP Search Problems
by: Ježil, Ondřej
Published: (2023)
by: Ježil, Ondřej
Published: (2023)
Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
by: Digulescu, Mircea-Adrian
Published: (2026)
by: Digulescu, Mircea-Adrian
Published: (2026)