My first level! It's... pretty different from all the other levels on here, at least.
As the title suggests, the level walks through a proof that determining the solvability of a VVVVVV level is NP-hard. (Spoiler: we reduce to 3-SAT.) After some (very) lengthy exposition, an example is given to demonstrate how a particular instance of 3-SAT would be represented and solved.
The layout loosely resembles an academic paper. If you don't know anything about complexity theory then this whole thing probably won't make any sense at all, but if you have a passing familiarity with NP-completeness then I think you should be able to follow what I did here.
It's a 5x5 level, and every room is used. Difficulty-wise there are almost no dexterity challenges, but if you're unfamiliar with Boolean logic then you might find it confusing anyway.
Hope you all enjoy it!
CHANGELOG:
Version 1.0 (Released Oct. 1, 2011)
-Initial release.
As the title suggests, the level walks through a proof that determining the solvability of a VVVVVV level is NP-hard. (Spoiler: we reduce to 3-SAT.) After some (very) lengthy exposition, an example is given to demonstrate how a particular instance of 3-SAT would be represented and solved.
The layout loosely resembles an academic paper. If you don't know anything about complexity theory then this whole thing probably won't make any sense at all, but if you have a passing familiarity with NP-completeness then I think you should be able to follow what I did here.
It's a 5x5 level, and every room is used. Difficulty-wise there are almost no dexterity challenges, but if you're unfamiliar with Boolean logic then you might find it confusing anyway.
Hope you all enjoy it!
CHANGELOG:
Version 1.0 (Released Oct. 1, 2011)
-Initial release.