Cover Image

King Chasing Problem in Chinese Chess is NP-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Chao, Zhang, Zhujun, Yang, Chao
Format:	Preprint
Published:	2026
Subjects:	Combinatorics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
by: Yang, Chao, et al.
Published: (2024)

Undecidability of tiling the plane with a fixed number of Wang bars
by: Yang, Chao, et al.
Published: (2024)

A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
by: Yang, Chao, et al.
Published: (2024)

Atropos-k is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
by: Yang, Chao, et al.
Published: (2024)

Translational Aperiodic Sets of 7 Polyominoes
by: Yang, Chao, et al.
Published: (2024)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

Friends-and-strangers is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling with Three Tiles
by: Yang, Chan, et al.
Published: (2024)

A Wild Sheep Chase Through an Orchard
by: Dempsey, Jordan, et al.
Published: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
by: Minevich, Igor, et al.
Published: (2024)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

Direct Product Primality Testing of Graphs is GI-hard
by: Calderoni, Luca, et al.
Published: (2020)

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

Hardness of Finding Kings and Strong Kings
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Between proper and square coloring of planar graphs, hardness and extremal graphs
by: Delépine, Thomas
Published: (2026)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Real Stability and Log Concavity are coNP-Hard
by: Chin, Tracy
Published: (2024)

Parameterised Holant Problems
by: Aivasiliotis, Panagiotis, et al.
Published: (2024)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

The Rank-Ramsey Problem and the Log-Rank Conjecture
by: Beniamini, Gal, et al.
Published: (2024)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
by: Gaspers, Serge, et al.
Published: (2025)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
by: Grüne, Christoph
Published: (2022)

On the hardness of recognizing graphs of small mim-width and its variants
by: la Tour, Max Dupré, et al.
Published: (2025)

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
by: Ikenmeyer, Christian, et al.
Published: (2022)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

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

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

On Computational Aspects of Ordered Matching Problems
by: Čertík, Michal, et al.
Published: (2025)

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
by: Li, Xin, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
by: Bhangale, Amey, et al.
Published: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
by: Bhangale, Amey, et al.
Published: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
by: Han, Zicheng, et al.
Published: (2026)