Ripple Effect is NP-complete

Ripple Effect is NP-complete. We reduce from 3-SAT.

The wire is of this form:

Wire in Ripple Effect

3’s carry the value True, 2’s carry the value False. We also keep track of the orientation, as reversing the orientation reverses the value carried by the wire. It can easily be shown that those two are the only local solutions. The gray squares will combine into a single region that will be filled by numbers appropriately.

We can “stretch” the wire arbitrarily long by inserting 4, 5, 6, and so on:

Phase Shifter in Ripple Effect

We can also bend wires:

Corner in Ripple Effect

And cross them:

Crossover in Ripple Effect

Now that the basics are set, time to head to the more advanced gadgets:

To put an input:

Input in Ripple Effect

To branch wires:

Branch in Ripple Effect

We only need one more gadget, the NAND gate.

NAND Gate in Ripple Effect

Whose local solutions are:

(True/True)

NAND, with True/True input

(True/False; for False/True, flip)

NAND, with True/False input

(False/False)

NAND, with False/False input

With these gadgets, we can construct every possible Boolean formula or truth table, since we can create NOT, AND, OR, and TRUE:

NAND, symbolic form

NOT from NAND

AND from NAND

OR from NAND

TRUE from NAND

And we can combine them in straightforward ways:

Sample truth table and its realization with NOT, AND, and OR gates

We can also combine them into an instance of 3-SAT, more or less following the above pattern (ORing the three literals in a clause and setting its result to TRUE).

This proves that Ripple Effect is NP-complete.

For fun, here’s a puzzle that simulates the equation \neg (x \wedge \neg x) = x:

A Ripple Effect puzzle that simulates x NAND -x = x

Ripple Effect: x NAND -x = x

However, a faster result by betaveros, if we take Latin Square as NP-complete:

Puzzle 75a: Latin Square

Puzzle 75: TomTom is NP-complete
Latin Square

Puzzle 75: Ripple Effect

Puzzle 75: TomTom Ripple Effect is NP-complete
Ripple Effect

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s