Buchumschlag

Hive is PSPACE-Hard

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Andel, Daniël, Rin, Benjamin
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity 91A46 (Primary) 68Q17 (Secondary) F.1.3; F.2.2
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Quoridor is PSPACE-Complete
von: Drop, Marius, et al.
Veröffentlicht: (2026)

Battle Sheep is PSPACE-complete
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Col is PSPACE-complete on Triangular Grids
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Two-player Domino games
von: de Menibus, Benjamin Hellouin, et al.
Veröffentlicht: (2023)

Paintbucket on graphs is PSPACE-complete
von: Saunders, Ethan J., et al.
Veröffentlicht: (2024)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
von: Lela, Marko
Veröffentlicht: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
von: Kelley, Zander, et al.
Veröffentlicht: (2023)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
von: Burke, Kyle, et al.
Veröffentlicht: (2024)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
von: Hakoniemi, Tuomas, et al.
Veröffentlicht: (2024)

NP-hardness of p-adic linear regression
von: Baker, Gregory D.
Veröffentlicht: (2026)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
von: Dorochko, Leonid, et al.
Veröffentlicht: (2026)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
von: Rossman, Benjamin
Veröffentlicht: (2024)

Computational Complexity of Determining the Assembly Index
von: Masierak, Piotr
Veröffentlicht: (2026)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
von: Lela, Marko
Veröffentlicht: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
von: Lela, Marko
Veröffentlicht: (2025)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
von: Saffidine, Abdallah, et al.
Veröffentlicht: (2025)

Separation of PSPACE and EXP
von: Czerwinski, Reiner
Veröffentlicht: (2021)

Shifted Partial Derivative Polynomial Rank and Codimension
von: Edwards, Darren J.
Veröffentlicht: (2025)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Quantum algorithms through graph composition
von: Cornelissen, Arjan
Veröffentlicht: (2025)

Quantum walks through generalized graph composition
von: Cornelissen, Arjan
Veröffentlicht: (2025)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
von: Shalunov, Yakov
Veröffentlicht: (2023)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
von: Grochow, Joshua A., et al.
Veröffentlicht: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
von: Philip, Geevarghese, et al.
Veröffentlicht: (2026)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
von: Eua-anant, Pakapim, et al.
Veröffentlicht: (2025)

On Small-depth Frege Proofs for PHP
von: Håstad, Johan
Veröffentlicht: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
von: Levin, Leonid A.
Veröffentlicht: (2022)

On the computational complexity of Data Flow Analysis
von: Sood, Gaurav, et al.
Veröffentlicht: (2013)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
von: Susukita, Kosuke, et al.
Veröffentlicht: (2026)

A correspondence between the time and space complexity
von: Latkin, Ivan V.
Veröffentlicht: (2023)

I/O complexity and pebble games with partial computations
von: Sobczyk, Aleksandros
Veröffentlicht: (2024)

A Characterization of Complexity in Public Goods Games
von: Gilboa, Matan
Veröffentlicht: (2023)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
von: Böhnlein, Toni, et al.
Veröffentlicht: (2024)

Computational Hardness of Reinforcement Learning with Partial $q^π$-Realizability
von: Karimi, Shayan, et al.
Veröffentlicht: (2025)

Finitely (In)tractable Promise Constraint Satisfaction Problems
von: Asimi, Kristina, et al.
Veröffentlicht: (2020)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
von: Bodnar, Levente
Veröffentlicht: (2024)

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
von: Emmerich, Michael T. M., et al.
Veröffentlicht: (2026)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
von: von Liechtenstein, Maximilian R. P.
Veröffentlicht: (2025)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
von: Huseynzade, Rafig
Veröffentlicht: (2025)