Escape Level : "Gangnails!" by Brian Potetz (with some help from the ancients)

« back Browsing Levels: #378 "Gangnails!"


prev: #377 "108% Fat Free"	next: #379 "Laser Democracy in the Heartland"

"Gangnails!" by Brian Potetz (with some help from the ancients)

added 26 Feb 2005 17:14

Solved 59/59

Cooked 0/59

Difficulty 2.10

Style 5.18

Rigidity 7.25

Shortest Solution
By Doom

On 30 Mar 2005 10:47

Comments (turn spoilers on)

450 Gangnails! Max (61) Mon 28 Feb 2005 00:07

Hey, this is pretty neat. I got a nice "surprise" at the end, too!

440 Gangnails! Tom 7 (1) Sun 27 Feb 2005 11:31

Cool, thanks! This is very simple, huh...

So know it is known that:
(1) Escape solvability is NP-hard (Several embeddings, or (2))
(2) Escape solvability is PSPACE-hard (Sokoban reduction + Sokoban PSPACE-completeness)
(3) Escape solvability is probably not in NP, unless there is some method for short-cutting the discovery of exponential solutions like this.
(4) Escape solvability should be in NPSPACE (no need to save the solution as you go, and the game only needs poly space (actually constant!) to execute moves), which means that it is in PSPACE since PSPACE=NPSPACE.
(5) Escape is PSPACE-complete (2, 4) and not NP-complete unless NP=PSPACE.

(I am not an expert on this stuff!)

Comments (turn spoilers on)

450	Gangnails!	Max (61)	Mon 28 Feb 2005 00:07
	Hey, this is pretty neat. I got a nice "surprise" at the end, too!

440	Gangnails!	Tom 7 (1)	Sun 27 Feb 2005 11:31
	Cool, thanks! This is very simple, huh... So know it is known that: (1) Escape solvability is NP-hard (Several embeddings, or (2)) (2) Escape solvability is PSPACE-hard (Sokoban reduction + Sokoban PSPACE-completeness) (3) Escape solvability is probably not in NP, unless there is some method for short-cutting the discovery of exponential solutions like this. (4) Escape solvability should be in NPSPACE (no need to save the solution as you go, and the game only needs poly space (actually constant!) to execute moves), which means that it is in PSPACE since PSPACE=NPSPACE. (5) Escape is PSPACE-complete (2, 4) and not NP-complete unless NP=PSPACE. (I am not an expert on this stuff!)