Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.02622 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Similar Items
PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
by: Scheder, Dominik, et al.
Published: (2025)
by: Scheder, Dominik, et al.
Published: (2025)
Corrigendum: PLS is contained in PLC
by: Ishizuka, Takashi
Published: (2023)
by: Ishizuka, Takashi
Published: (2023)
On the computational power of $C$-random strings
by: Milovanov, Alexey
Published: (2024)
by: Milovanov, Alexey
Published: (2024)
Matchgate signatures under variable permutations
by: Meng, Boning, et al.
Published: (2025)
by: Meng, Boning, et al.
Published: (2025)
Limit on the computational power of $\mathrm{C}$-random strings
by: Milovanov, Alexey
Published: (2026)
by: Milovanov, Alexey
Published: (2026)
BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)
by: Ishibashi, Takehiro, et al.
Published: (2025)
Quantum circuits for permutation matrices
by: Hanson, Jason
Published: (2025)
by: Hanson, Jason
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)
Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
by: Binnendyk, Eric
Published: (2025)
by: Binnendyk, Eric
Published: (2025)
The PPP-completeness of the Ward-Szabo theorem
by: Ishizuka, Takashi
Published: (2025)
by: Ishizuka, Takashi
Published: (2025)
Topological entropy of Turing complete dynamics
by: Bruera, Renzo, et al.
Published: (2024)
by: Bruera, Renzo, et al.
Published: (2024)
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)
On the local consequence of modal Product logic: standard completeness and decidability
by: Vidal, Amanda
Published: (2023)
by: Vidal, Amanda
Published: (2023)
Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
by: DeStefano, Zachary, et al.
Published: (2025)
by: DeStefano, Zachary, et al.
Published: (2025)
Two bases suffice for QMA1-completeness
by: Ma, Henry, et al.
Published: (2025)
by: Ma, Henry, et al.
Published: (2025)
Ask, and it shall be given: On the Turing completeness of prompting
by: Qiu, Ruizhong, et al.
Published: (2024)
by: Qiu, Ruizhong, et al.
Published: (2024)
Polynomial-time completion of phylogenetic tree sets
by: Koshkarov, Aleksandr, et al.
Published: (2026)
by: Koshkarov, Aleksandr, 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)
Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
by: Ani, Hayashi, et al.
Published: (2024)
by: Ani, Hayashi, et al.
Published: (2024)
Atropos-k is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)
by: Yang, Chao, et al.
Published: (2024)
The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)
by: Zhuk, Dmitriy, et al.
Published: (2021)
Isotropy and completeness indices of multilinear maps
by: Chen, Qiyuan, et al.
Published: (2025)
by: Chen, Qiyuan, et al.
Published: (2025)
The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete
by: Nelson, Jon, et al.
Published: (2025)
by: Nelson, Jon, et al.
Published: (2025)
Time complexity for deterministic string machines
by: Cataltepe, Ali, et al.
Published: (2024)
by: Cataltepe, Ali, et al.
Published: (2024)
Maker-Maker games of rank 4 are PSPACE-complete
by: Galliot, Florian, et al.
Published: (2025)
by: Galliot, Florian, et al.
Published: (2025)
Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
by: Concha-Vega, Pablo
Published: (2026)
by: Concha-Vega, Pablo
Published: (2026)
DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
by: Ji, Zhengfeng, et al.
Published: (2026)
by: Ji, Zhengfeng, et al.
Published: (2026)
Metastability-Containing Turing Machines
by: Bund, Johannes, et al.
Published: (2026)
by: Bund, Johannes, et al.
Published: (2026)
Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
by: Liu, Yuxi
Published: (2025)
by: Liu, Yuxi
Published: (2025)
Hardness Results on Characteristics for Elastic-Degenerated Strings
by: Köppl, Dominik, et al.
Published: (2024)
by: Köppl, Dominik, et al.
Published: (2024)
Verifying Quantized Graph Neural Networks is PSPACE-complete
by: Sälzer, Marco, et al.
Published: (2025)
by: Sälzer, Marco, et al.
Published: (2025)
A conservative Turing complete $S^4$ flow
by: Suárez-Serrato, Pablo
Published: (2023)
by: Suárez-Serrato, Pablo
Published: (2023)
Pathways to Tractability for Geometric Thickness
by: Depian, Thomas, et al.
Published: (2024)
by: Depian, Thomas, et al.
Published: (2024)
4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
by: Galliot, Florian
Published: (2025)
by: Galliot, Florian
Published: (2025)
PPSZ is better than you think
by: Scheder, Dominik
Published: (2022)
by: Scheder, Dominik
Published: (2022)
Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete
by: Ghosh, Avijeet, et al.
Published: (2025)
by: Ghosh, Avijeet, et al.
Published: (2025)
Has quantum advantage been achieved?
by: Hangleiter, Dominik
Published: (2026)
by: Hangleiter, Dominik
Published: (2026)
On the completeness of several fortification-interdiction games in the Polynomial Hierarchy
by: Tomasaz, Alberto Boggio, et al.
Published: (2024)
by: Tomasaz, Alberto Boggio, et al.
Published: (2024)
Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
by: Rudolph, Dorian, et al.
Published: (2024)
by: Rudolph, Dorian, et al.
Published: (2024)
Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)
by: Ghosh, Soumik, et al.
Published: (2024)