Cover Image

Baba is You is Undecidable

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Geller, Jonathan
Format:	Preprint
Published:	2022
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
by: MIT Hardness Group, et al.
Published: (2024)

On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes
by: Kolář, Martin
Published: (2026)

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
by: Li, Yaqiao
Published: (2025)

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

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

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
by: Li, Cheuk Ting
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 Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
by: Yang, Chao, et al.
Published: (2024)

Undecidability and incompleteness in quantum information theory and operator algebras
by: Goldbring, Isaac
Published: (2024)

Computational Irreducibility as the Foundation of Agency: A Formal Model Connecting Undecidability to Autonomous Behavior in Complex Systems
by: Azadi, Poria
Published: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Undecidability of the block gluing classes of homshifts
by: Chandgotia, Nishant, et al.
Published: (2025)

Positive Moments Forever: Undecidable and Decidable Cases
by: Coves, Gemma De les, et al.
Published: (2024)

The Equivalence Problem of E-Pattern Languages with Regular Constraints is Undecidable
by: Nowotka, Dirk, et al.
Published: (2024)

The Equivalence Problem of E-Pattern Languages with Length Constraints is Undecidable
by: Nowotka, Dirk, et al.
Published: (2024)

Can You Link Up With Treewidth?
by: Curticapean, Radu, et al.
Published: (2024)

Emit As You Go: Enumerating Edges of a Spanning Tree
by: Casel, Katrin, et al.
Published: (2025)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
by: Doron, Dean, et al.
Published: (2024)

Looped ReLU MLPs May Be All You Need as Practical Programmable Computers
by: Liang, Yingyu, et al.
Published: (2024)

Punctured Low-Bias Codes Behave Like Random Linear Codes
by: Guruswami, Venkatesan, et al.
Published: (2021)

On the Number of Quantifiers Needed to Define Boolean Functions
by: Carmosino, Marco, et al.
Published: (2024)

Multi-Structural Games and Beyond
by: Carmosino, Marco, et al.
Published: (2023)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
by: Lykov, Danylo, et al.
Published: (2022)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
by: Guruswami, Venkatesan, et al.
Published: (2021)

Fine-Grained Classification Of Detecting Dominating Patterns
by: Dransfeld, Jonathan, et al.
Published: (2025)

Parallel Play Saves Quantifiers
by: Carmosino, Marco, et al.
Published: (2024)

Reconfiguring Graph Homomorphisms on the Sphere
by: Lee, Jae-Baek, et al.
Published: (2018)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
by: Laakkonen, Tuomas, et al.
Published: (2022)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
by: Biswas, Aniruddha, et al.
Published: (2022)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

The Complexity of Contracting Bipartite Graphs into Small Cycles
by: Krithika, R., et al.
Published: (2022)

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

On Matrix Multiplication and Polynomial Identity Testing
by: Andrews, Robert
Published: (2022)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
by: Arvind, V., et al.
Published: (2022)

On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
by: Devillers, Raymond, et al.
Published: (2022)

The Stochastic Arrival Problem
by: Webster, Thomas
Published: (2022)