Started by Buttons, October 01, 2011, 05:41:57 PM
Quote from: Martze on October 02, 2011, 12:04:17 AMI can't see the practical use of the result, but it was a fun read.
Quote from: Martze on October 02, 2011, 12:04:17 AMOf course, this only works for generalized VVVVVV, that is, without the 20x20 size constraint.
Quote from: Martze on October 02, 2011, 12:04:17 AMhttp://www.destructoid.com/blogs/knutaf/a-mathematical-and-inquisitive-approach-to-vvvvvv-184093.phtml
Quote from: Buttons on October 01, 2011, 05:41:57 PMAs 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.
Quote from: Buttons on October 01, 2011, 05:41:57 PMThe 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.
Quote from: PJBottomz on October 02, 2011, 03:19:39 AMIf I understood half of that... I might actually play it. But WHAT THE HELL ARE YOU EVEN TALKING ABOUT?!
Quote from: Martze on October 02, 2011, 03:19:04 AMYeah. VVVVVV without flags may very well be in NP!
Quote from: The Brass on October 02, 2011, 07:24:09 AMAwesome, awesome work. Always nice to learn something new. Nice to see such passion for this game. Great level design, too. Just one flaw - the crewmates can be skipped. I suggest you use gravlines to block the exit wires, and place a [flag(X, on) destroy(gravitylines)] script on top of the crewmate, and [ifflag(X, [destroy(gravitylines)]] on the entrances. That way you only have to beat the challenge once.
Quote from: cams on October 03, 2011, 04:43:13 PMI just beat the level but I have no idea what you're talking about... Can Terry confirm this? Is VVVVVV really NP-Hard? (Whatever that means)