Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.21332 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Similar Items
Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)
by: Hirahara, Shuichi, et al.
Published: (2025)
NP-hardness of SVP in Euclidean Space
by: Wan, Daqing
Published: (2026)
by: Wan, Daqing
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)
Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)
by: Leipold, Karla, et al.
Published: (2024)
King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)
by: Li, Chao, et al.
Published: (2026)
Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)
by: Piddock, Stephen
Published: (2025)
An even simpler hard variant of Not-All-Equal 3-SAT
by: Darmann, Andreas, et al.
Published: (2024)
by: Darmann, Andreas, et al.
Published: (2024)
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
by: Baraskar, Omkar, et al.
Published: (2024)
by: Baraskar, Omkar, et al.
Published: (2024)
Prove Symbolic Regression is NP-hard by Symbol Graph
by: Song, Jinglu, et al.
Published: (2024)
by: Song, Jinglu, et al.
Published: (2024)
Data Debugging is NP-hard for Classifiers Trained with SGD
by: Guo, Zizheng, et al.
Published: (2024)
by: Guo, Zizheng, et al.
Published: (2024)
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)
Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)
by: Krokhin, Andrei, et al.
Published: (2025)
Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)
by: Blanc, Guy, et al.
Published: (2025)
The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)
by: Gu, Shouzhen, et al.
Published: (2026)
Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
by: Ron-Zewi, Noga, et al.
Published: (2024)
by: Ron-Zewi, Noga, et al.
Published: (2024)
Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)
by: MIT Gadgets Group, et al.
Published: (2020)
P=NP
by: Deng, Zikang
Published: (2024)
by: Deng, Zikang
Published: (2024)
Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)
by: Gordeev, Lev, et al.
Published: (2023)
On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)
by: Krajicek, Jan
Published: (2025)
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)
Spatial Voting with Incomplete Voter Information
by: Imber, Aviram, et al.
Published: (2023)
by: Imber, Aviram, et al.
Published: (2023)
Constant Degree Direct Product Testers with Small Soundness
by: Bafna, Mitali, et al.
Published: (2024)
by: Bafna, Mitali, et al.
Published: (2024)
Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)
by: Antonelli, Melissa, et al.
Published: (2025)
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)
BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)
by: Ishibashi, Takehiro, 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)
Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
by: Gezer, M. Utkan, et al.
Published: (2020)
by: Gezer, M. Utkan, et al.
Published: (2020)
NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)
by: Baker, Gregory D.
Published: (2026)
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)
The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)
by: Fuchs, Janosch, et al.
Published: (2023)
Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
by: He, Entong
Published: (2024)
by: He, Entong
Published: (2024)
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)
Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by: Heeger, Klaus, et al.
Published: (2024)
by: Heeger, Klaus, et al.
Published: (2024)
On the Structure of Hamiltonian Graphs with Small Independence Number
by: Jedličková, Nikola, et al.
Published: (2024)
by: Jedličková, Nikola, et al.
Published: (2024)
Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)
by: Cavalar, Bruno, et al.
Published: (2025)
NP-Completeness of Multicast Beamforming in Wireless Communication
by: Shrestha, Sagar
Published: (2025)
by: Shrestha, Sagar
Published: (2025)