Smullyan's clever solutions

In my post about Raymond Smullyan’s Og and Bog puzzle, I wrote:

Smullyan has a clever solution in the back of Logical Labyrinths, but I’m going to whittle the puzzle down to a size I can hold in my head, because I like procedures to solve puzzles. Having a procedure keeps me from making mistakes, and developing the procedure helps me understand the underpinnings of all problems.

I thought of something that makes Smullyan smarter than I believed.

My method of solving the Og and Bog Puzzle was to write a propositional logic expression that encapsulated the puzzle, then create a truth table for that expression. After creating the truth table, I had to look through the truth table to find the true/false values for the logical variables that made the entire propositional logic expression evaluate to true.

This is exactly the Satisfiability Problem (mostly called “SAT”). It turns out that SAT is one of those NP-complete problems, and it’s very hard in general. That is, the time to solve a satisfiability problem goes up very rapidly as the number of logical variables in the expression increases. It might be fast to solve a 4-logical-variable problem like Og and Bog, but it will take a lot more than twice as long to solve an 8-logical-variable problem, and it will take very long indeed to solve a 20-variable problem.

Smullyan’s clever solutions circumvent the increasing time it takes to solve propositional logic problems. Smullyan took advantage of individual peculiarities in his puzzles. He didn’t have a general way to do this, he didn’t prove P = NP or anything like that.