2009/05/14 by Daniel Gottesman, Gottesman, Daniel, Sandy Irani +1 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0905.2419
openalex publication_date 2009/05/14 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
We study the complexity of a class of problems involving satisfying\nconstraints which remain the same under translations in one or more spatial\ndirections. In this paper, we show hardness of a classical tiling problem on an\nN x N 2-dimensional grid and a quantum problem involving finding the ground\nstate energy of a 1-dimensional quantum system of N particles. In both cases,\nthe only input is N, provided in binary. We show that the classical problem is\nNEXP-complete and the quantum problem is QMAEXP-complete. Thus, an algorithm\nfor these problems which runs in time polynomial in N (exponential in the input\nsize) would imply that EXP = NEXP or BQEXP = QMAEXP, respectively. Although\ntiling in general is already known to be NEXP-complete, to our knowledge, all\nprevious reductions require that either the set of tiles and their constraints\nor some varying boundary conditions be given as part of the input. In the\nproblem considered here, these are fixed, constant-sized parameters of the\nproblem. Instead, the problem instance is encoded solely in the size of the\nsystem.\n