Cover Image

NP-Completeness Proofs of Puzzles using the T-Metacell Framework

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kiatchaipipat, Nattapol, Ruangwises, Suthee
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
by: Ruangwises, Suthee
Published: (2024)

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)

Thin Tree Verification is coNP-Complete
by: Moayyedi, Alice
Published: (2025)

Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework
by: Lee, Changryeol
Published: (2026)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
by: Fairbairn, David L., et al.
Published: (2024)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
by: Istrate, Gabriel
Published: (2024)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
by: Gupta, Chetan, et al.
Published: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
by: Fritsch, Timo, et al.
Published: (2026)

Fast Simulation of Cellular Automata by Self-Composition
by: Natal, Joseph, et al.
Published: (2024)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

Direct Sums for Parity Decision Trees
by: Besselman, Tyler, et al.
Published: (2024)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
by: Knop, Dušan, et al.
Published: (2017)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
by: Lobe, Elisabeth, et al.
Published: (2021)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
by: de Rezende, Susanna F., et al.
Published: (2026)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
by: Diaby, Moustapha, et al.
Published: (2023)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
by: Bartlett, Celina Janet
Published: (2025)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
by: Lagerkvist, Victor, et al.
Published: (2025)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
by: Bodirsky, Manuel, et al.
Published: (2026)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
by: van Brügge, Jan
Published: (2024)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
by: Clinch, Katie, et al.
Published: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

Sumplete is Hard, Even with Two Different Numbers
by: Ruangwises, Suthee
Published: (2023)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
by: Lingas, Andrzej
Published: (2026)

Quoridor is PSPACE-Complete
by: Drop, Marius, et al.
Published: (2026)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Complexity of Firefighting on Graphs
by: Althoetmar, Julius, et al.
Published: (2025)