Escape Level : "Satisfiability" by mjn

« back Browsing Levels: #290 "Satisfiability"


prev: #289 "Self-destruct Panels"	next: #291 "Across the 8th Dimension"

"Satisfiability" by mjn

added 15 Sep 2004 02:14

Solved 59/59

Cooked 1/59

Difficulty 1.91

Style 4.66

Rigidity 4.47

Shortest Solution
Name Speed Record

Length 90 moves

By Zoogie

On 01 Apr 2005 10:20

Comments (turn spoilers off)

4979 Satisfiability Cheryl (807) Sun 01 Jan 2006 20:23 SPOILER

Cook: There are so many different combinations, can you even keep track?

1238 Satisfiability Zoogie (317) Fri 01 Apr 2005 10:20 SPOILER

Added speedrun: 90 moves (old: 92).

1040 Satisfiability Doom (371) Wed 30 Mar 2005 10:53 SPOILER

Added speedrun: 92 moves (old: 999999).

94 Satisfiability Tom 7 (1) Wed 15 Sep 2004 09:06

Cool! Yes, this would show that it's NP-hard. To show that it's NP-complete, you'd need to show that it's also in NP. That would mean that we could verify that a level has a solution in time polynomial to its size, once given a solution. It is certainly polynomial to verify a polynomial-size solution, but it is not obvious to me that every solvable level has a polynomial-size solution. (ie, some levels may be VERY HARD in the sense that they require an exponential number of moves.) Since Escape embeds several other games such as Sokoban and (sort of) the UFO puzzle, there may already exist some results that imply it is harder than NP (unfortunately the other direction would probably have to be a new theorem).

93 Satisfiability mjn (118) Wed 15 Sep 2004 02:23

I think the "determine if an Escape level has a solution" problem is NP-complete: here's one way to reduce an instance of SAT to an Escape level.
Each row of stop signs is a variable, and the gadgets on the left let you assign "true" or "false" by sending you through a chain of teleports. This level is (A or B) and (not A or B or C) and (not B or not C).

Been a while since theory class--is there something to be proved in the other direction, too?

Comments (turn spoilers off)

4979	Satisfiability	Cheryl (807)	Sun 01 Jan 2006 20:23	SPOILER
	Cook: There are so many different combinations, can you even keep track?

1238	Satisfiability	Zoogie (317)	Fri 01 Apr 2005 10:20	SPOILER
	Added speedrun: 90 moves (old: 92).

1040	Satisfiability	Doom (371)	Wed 30 Mar 2005 10:53	SPOILER
	Added speedrun: 92 moves (old: 999999).

94	Satisfiability	Tom 7 (1)	Wed 15 Sep 2004 09:06
	Cool! Yes, this would show that it's NP-hard. To show that it's NP-complete, you'd need to show that it's also in NP. That would mean that we could verify that a level has a solution in time polynomial to its size, once given a solution. It is certainly polynomial to verify a polynomial-size solution, but it is not obvious to me that every solvable level has a polynomial-size solution. (ie, some levels may be VERY HARD in the sense that they require an exponential number of moves.) Since Escape embeds several other games such as Sokoban and (sort of) the UFO puzzle, there may already exist some results that imply it is harder than NP (unfortunately the other direction would probably have to be a new theorem).

93	Satisfiability	mjn (118)	Wed 15 Sep 2004 02:23
	I think the "determine if an Escape level has a solution" problem is NP-complete: here's one way to reduce an instance of SAT to an Escape level. Each row of stop signs is a variable, and the gadgets on the left let you assign "true" or "false" by sending you through a chain of teleports. This level is (A or B) and (not A or B or C) and (not B or not C). Been a while since theory class--is there something to be proved in the other direction, too?