Talk:I Wanna Be the Esolang

Computational class

This language isn't fully specified yet, so I can't give a detailed proof, but unless there's something that prevents it (e.g. the player character having no way to return to higher areas of the level an indefinite number of times even with very helpful level geometry, or level trigger…switch wall connections being unable to cross each other), this language is highly likely to be PSPACE-complete.

The basic idea is to model a board-game-like puzzle using a number of level triggers that each model the concept of "game object X is at location Y" – they're switched off if it isn't and switched on if it is. You can then create corridors (or more likely vertical shafts, to prevent backtracking to hit a trigger twice by forcing the triggers to be hit while falling) which simulate legal moves within the game by forcing the player to hit a sequence of triggers (turning some of them off and some of them on), and using switch walls in order to ensure that the player can only reach the corridor/shaft if the move would be legal (and to ensure that the player can only reach the goal if the puzzle is in a winning state). There are a range of PSPACE-complete puzzles that can be straightforwardly simulated like this.

The above proof assumes that level triggers work multiple times (which is probably the more interesting version of the language) – a version of the language in which they only work once would probably be NP-complete instead. --ais523 17:58, 13 February 2022 (UTC)