Monday, June 23, 2008

Jig-saw puzzle: to recognize vs. to do

In the Meno, Socrates spoke of the apparent paradox that we can recognize something that we have a harder time creating. In computer science this is often thought of as the P =? NP problem. There are many problems for which one can tell in Polynomial time whether a proposed solution is actually a solution but for which no one knows of a way to solve a typical instance of the problem in less than exponential (non-deterministic polynomial) time. The prototypical example is to find a set of values for Boolean variables that cause a Boolean expression to evaluate to true. Given a proposed set of values, it is trivial to determine whether the expression evaluates to true. But in general it is very time-consuming to find such a set of values or to determine that no such set exists.

That was brought to mind when a common-place intuitive example of this sort of problem occurred to me: a jig-saw puzzle. It's easy to tell whether a given configuration of jig-saw puzzle pieces is the correct one. But given a box full of pieces it may be a very time-consuming task to put them together correctly.

No comments: