Cover Image

Evolomino is NP-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Nikolaev, Andrei V.
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Combinatorics 68Q25, 03D15 F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

The Optimizer Quotient and the Certification Trilemma
by: Simas, Tristan
Published: (2026)

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
by: Alpay, Faruk, et al.
Published: (2026)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

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

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
by: Bannach, Max, et al.
Published: (2025)

Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

The Gallai Vertex Problem is $Θ_2^p$-Complete
by: Nikabadi, Amir, et al.
Published: (2026)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

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)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

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

Why the classes P and NP are not well-defined finitarily
by: Anand, Bhupinder Singh
Published: (2024)

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

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

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

The Polynomial Hierarchy does not collapse
by: Czerwinski, Reiner
Published: (2024)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)

Locality, Consistency, and the Tractability Frontier
by: Simas, Tristan
Published: (2026)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2024)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
by: Wulf, Lasse
Published: (2025)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

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

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

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

Computing Non-Repetitive Sequences with a Computable Lefthanded Local Lemma
by: Mourad, Daniel
Published: (2024)

Complexity and Enumeration in Models of Genome Rearrangement
by: Bailey, Lora, et al.
Published: (2023)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
by: DasGupta, Bhaskar, et al.
Published: (2026)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)

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

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

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
by: Phillips, Reed
Published: (2026)