Vi bevisar att en variant av 2048, en populär online pusselspel, är PSPACE-Complete. Vårt hårdhetsresultat håller för en version av problemet där spelaren har oracle tillgång till datorspelarens rörelser. Specifikt visar vi att för en n × n spelplan G, beräkning av en sekvens av rörelser för att nå en viss konfiguration C från en inledande konfiguration C 0 är PSPACE-Complete. Vår minskning är från Nondeterministic Constraint Logic (NCL). Vi visar också att avgöra om det finns en fast sekvens av drag S  med eller inte är en fast sekvens av drag S  på spelbordet är fastparameterdragbar (FPT). Vi beskriver en algoritm för att lösa detta problem i O(4 k n 2 ) tid.
Mehta visade att n × n versionen av spelet 2048 är PSPACE hård REF förutsatt att slumpmässiga rörelser är kända i förväg.
2048 is (PSPACE) Hard, but Sometimes Easy
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}