## VVVVVV is NP-Hard: A level-as-proof

Started by Buttons, October 01, 2011, 05:41:57 PM

#### Buttons

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.

#### Damn It AL to Hell

Pretty nice level, hard, but cool 10/10

#### Martze

Well that was interesting. I can't see the practical use of the result, but it was a fun read.

Of course, this only works for generalized VVVVVV, that is, without the 20x20 size constraint.

That reminds me of this:

http://www.destructoid.com/blogs/knutaf/a-mathematical-and-inquisitive-approach-to-vvvvvv-184093.phtml

I think Lemma B may be wrong due to the fact that Viridian has to accelerate to start and stop, but I'm not sure. Interesting read, anyway, if you liked this level.

#### Buttons

Vex69, you're a speed demon! I have no idea how you downloaded the level and read enough of the text to beat it and comment within 15 minutes of my post, but I'm super impressed.

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.
I'm a pure mathematician. Please don't use the p-word around me.

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.
Yup. Likewise, for the exercise I mentioned in the top-right terminal of the second room, you need to allow arbitrarily many flags rather than capping at 100. (At least in the solution I'm thinking of.)

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
Ha! Nice. I'm not sure I can parse the conditions in the theorem in a way that doesn't make it (a) trivial or (b) false, but the approach is pretty great.

#### Martze

Yeah. VVVVVV without flags may very well be in NP!

#### PJBottomz

Quote from: Buttons on October 01, 2011, 05:41:57 PM
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.

Uh, wat?

Quote from: Buttons on October 01, 2011, 05:41:57 PM
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.

Uh, wat?

If I understood half of that... I might actually play it. But WHAT THE HELL ARE YOU EVEN TALKING ABOUT?!

#### The Brass

Awesome, 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.

#### ThePaSch

Quote from: PJBottomz on October 02, 2011, 03:19:39 AM
If I understood half of that... I might actually play it. But WHAT THE HELL ARE YOU EVEN TALKING ABOUT?!

This level apparently isn't for you. You need to understand it in order to play it.

#### Buttons

Quote from: Martze on October 02, 2011, 03:19:04 AM
Yeah. VVVVVV without flags may very well be in NP!
You're totally right! Here's a proof, assuming fixed room size.

For a particular set of crewmates rescued and trinkets collected, the current "status" of a player in a flagless VVVVVV game is determined by the following choices:

-Position (choices bounded by a linear function in the number of rooms).

-Velocity (bounded by a constant).

-Current gravity direction (2 choices).

-Location of most recent checkpoint (bounded by a linear function in the number of rooms).

-Current status of crumbling platforms in current room (bounded by a very large constant).

-Current location and velocity of enemies in current room (bounded by an even larger constant).

-Current location and velocity of moving platforms in current room (same).

-Whether each scriptbox or terminal in the current room has been activated (bounded by an even larger constant).

-Whether grav lines, warp tokens, or platforms have been destroy()ed yet in the current room (8 choices).

And that's it, unless I'm forgetting something. So if we represent each combination of these choices as a vertex in a directed graph, and draw an edge from u to v if it's possible to get from state u to v in one tick of the game's clock (by some combination of pressing left, right, and/or action), then we've got a directed graph on a number of vertices that's quadratic in the number of rooms.

Some of those vertices (based on the position of Viridian) correspond to acquiring trinkets and some correspond to rescuing crewmen, and a solution involves picking those up in some particular sequence. But again, the number of trinkets (even ignoring the current cap at 20) and the number of crewmen (is there a cap? Even so....) is bounded by a linear function in the number of rooms.

So the total time to get from one position to the next trinket/crewman is O(n^2) since it's at most the diameter of the graph, and the total number of crewmates and trinkets is O(n), so the time to finish the level is O(n^3). Now granted, the cubic in question has a leading coefficient that's larger than the number of atoms in the universe, but a cubic is a cubic. So yay!

(Note: all of this falls apart if you let room sizes increase, like in The Tower but without the forced scrolling. I've almost succeeded in making a Towers of Hanoi puzzle using breaking platforms and moving enemies, to the point where I think a more clever designer could pull it off. Make a tall enough room and BAM! 2^n solving time.)

Quote from: PJBottomz on October 02, 2011, 03:19:39 AM
If I understood half of that... I might actually play it. But WHAT THE HELL ARE YOU EVEN TALKING ABOUT?!
Heh. No worries, you're only 14. But if you want to look up some of the terms you don't know on Wikipedia, I bet you'd find it enlightening and not that hard to understand. I learned most of this stuff when I was 16, and you seem like a reasonably smart kid, so it's worth a shot.

Quote from: The Brass on October 02, 2011, 07:24:09 AM
Awesome, 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.
Yeah, I thought about that. But as far as the proof is concerned there's no problem with crewmates getting skipped. The point is that a solution exists if and only if the formula can be satisfied, not that a solution is inevitable. So we only need to "idiot-proof" the level enough that an incorrect player can't win. It's fine if a correct player can lose, as long as it's because of other decisions he made. I decided to leave it this way, just so that the level itself could be constructed without scripts. (Well, besides the music ones.)

#### Damn It AL to Hell

#9
I just replayed this level again becuase I was bored and didn't want to work on my new level because a glitched terminal made me mad, and I just realized that the A's in the room you took a screenshot of, make one big A

You're stupid
Way to point out the obvious, Verdigris!
Okay smart asses, what's a Kelvin?
I don't know.
Then don't speak, or Dispenser may have you.
*gulp*

#### art begotti

Well, I beat the level, though I probably shouldn't have. My only previous experience with NP-anything is http://xkcd.com/287/ (and I suppose http://xkcd.com/399/ as well), and while I've had minor experience with Booleans, I had the hardest time wrapping my head around this problem. At first I assumed that the point of the problem was to find (please forgive any incorrect terminology I use) truth values for each variable such that each clause had exactly one true literal, but that would be pretty much impossible with just the first two clauses alone. My second problem was assuming that there was only one correct solution, even though I'm pretty you said somewhere that there was more than one solution, or at least two, or 16-10=6, or something like that. After beating it once, I went back and found another valid path. I'm not sure I get the whole NP system, but this was still a fun challenge. Now if you'll excuse me, I need to replenish my brain with a gallon of coffee.

#### cams

I 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)

#### Martze

Quote from: cams on October 03, 2011, 04:43:13 PM
I 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)

Just because he made the game doesn't necessarily mean he knows. Chess was invented LONG before complexity theory, so if you go back and ask the vizier who supposedly invented it if chess really is in PSPACE, he won't know what you're talking about.

People don't sit down and say "I'm going to make an NP-Complete game."

#### cams

#13
That was a half-serious, half-joke post.
Of course I didn't really expect Terry to know this stuff, I'm just curious on what he would say about this level.

#### Noyb

This is very clever!