Image de couverture de livre

A Simple Proof that Ricochet Robots is PSPACE-Complete

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Balanza-Martinez, Jose, Cantu, Angel A., Schweller, Robert, Wylie, Tim
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
par: Guruswami, Venkatesan, et autres
Publié: (2023)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2024)

Streaming Zero-Knowledge Proofs
par: Cormode, Graham, et autres
Publié: (2023)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Does Subset Sum Admit Short Proofs?
par: Włodarczyk, Michał
Publié: (2024)

Simple approximation algorithms for Polyamorous Scheduling
par: Biktairov, Yuriy, et autres
Publié: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
par: Nederlof, Jesper
Publié: (2026)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
par: Zhang, Bingwei, et autres
Publié: (2026)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
par: Frei, Fabian, et autres
Publié: (2024)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
par: Frei, Fabian, et autres
Publié: (2025)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
par: Gaspers, Serge, et autres
Publié: (2025)

On the Power of Interactive Proofs for Learning
par: Gur, Tom, et autres
Publié: (2024)

NP-Hardness and a PTAS for the Pinwheel Problem
par: Kleinberg, Robert, et autres
Publié: (2026)

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
par: Ganian, Robert, et autres
Publié: (2026)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
par: de Berg, Mark, et autres
Publié: (2025)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
par: Hirahara, Shuichi, et autres
Publié: (2023)

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
par: Goodrich, Michael T., et autres
Publié: (2024)

Testing Sumsets is Hard
par: Chen, Xi, et autres
Publié: (2024)

Recognizing Sumsets is NP-Complete
par: Abboud, Amir, et autres
Publié: (2024)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
par: Bai, Tian, et autres
Publié: (2026)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
par: Tate, Elise, et autres
Publié: (2025)

Second Price Matching with Complete Allocation and Degree Constraints
par: Pinchasi, Rom, et autres
Publié: (2025)

Learning Functions of Halfspaces
par: Alman, Josh, et autres
Publié: (2026)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
par: Jansen, Bart M. P., et autres
Publié: (2026)

Detecting Low-Degree Truncation
par: De, Anindya, et autres
Publié: (2024)

DNF formulas are efficiently testable with relative error
par: Chen, Xi, et autres
Publié: (2026)

Universal Solvability for Robot Motion Planning on Graphs
par: Dhar, Anubhav, et autres
Publié: (2025)

Lower Bounds for Convexity Testing
par: Chen, Xi, et autres
Publié: (2024)

Testing noisy low-degree polynomials for sparsity
par: Bao, Yiqiao, et autres
Publié: (2025)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2025)

A Note on Approximability of Densest At-Least-k-Subgraph
par: Laekhanukit, Bundit, et autres
Publié: (2026)

A Space-space Trade-off for Directed st-Connectivity
par: Edenhofer, Roman
Publié: (2026)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
par: Clinch, Katie, et autres
Publié: (2025)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
par: Lehner, Lisa, et autres
Publié: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
par: Braverman, Mark, et autres
Publié: (2024)

Computational Explorations of Total Variation Distance
par: Bhattacharyya, Arnab, et autres
Publié: (2024)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
par: Gholizadeh, Hossein, et autres
Publié: (2025)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
par: Ducoffe, Guillaume
Publié: (2026)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
par: Buhrman, Harry, et autres
Publié: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
par: Garg, Sumegha, et autres
Publié: (2026)