## A Roll In The Hay

Haystacks.  Haystacks, everywhere.

Let’s get something straight, all algorithms are exhaustive search.  We just need to find the right haystack.

In a previous post I talked about complexity theory getting off to a bizarre, albeit beautiful, start that ended us up in the land of decision problems.  So now we have decision problems and languages and grammars, when what we really wanted to be talking about were the inherent search problems they corresponded to.

Now some of us may have gotten very used to decision problems and they now seem natural, but there are some subtleties to keep in mind.  To get a taste of some of the weirdness of this contrast of decision vs. search, let’s take a look at a specific problem.  Let’s consider the classic NP-complete decision problem of 3-coloring a graph.

For completeness, the 3-COL is to, given a graph $G=(V,E)$, decide whether all of the vertices in $V$ can be each colored one of our 3 colors so that no two vertices that are connected by an edge in $E$ have the same color.

So, of course, we may say exhaustive search for this problem is the naïve algorithm that takes $3^{|V|}$ time by trying every possible coloring.  And since this problem is NP-complete we don’t expect to be able to do something really clever that allows us to only take polynomial time.  Moreover, the Exponential Time Hypothesis (ETH) conjectures that this exhaustive search is essentially the best we can do.  That is, to see if there’s a needle in this haystack, we have to go through every single piece of the $3^{|V|}$ pieces of hay!

But not exactly.  We can do a little better (even if it’s still an exponential run-time):

Instead of looking through every possible coloring to see if it’s a proper coloring, we could instead look for independent sets (a set of vertices that have no edges between them) where the rest of the graph is 2-colorable.  The trick here is that checking whether a graph is 2-colorable can be done in polynomial time!  And so, such an independent set exists if and only if the graph is 3-colorable since the independent set can be colored one color (by definition there’s no edges between these vertices and so there’s no clash of color) and then the rest can be colored with the other two colors.

Why is this useful?  I’m going to be really hand-wavy here and say we just need to look for independent sets of size less than or equal to $\frac{1}{3}|V|$ and so it takes (crassly) approximately $|V| \choose \leq\frac{1}{3}|V|$$\approx 3^{\frac{1}{3}|V|}\approx 1.45^{|V|}$ time to decide whether a graph is 3-colorable with this approach (for more detail that’s still at a high level, see this).  So this is still exponential, but $1.45^{|V|}$ is still much better than the naïve $3^{|V|}$.  (Note that this doesn’t contradict ETH since it’s still an exponentially big haystack in which we need to turn over every single piece of hay).

This type of work generally lies in the area of Exact Exponential Algorithms which is mainly concerned with finding improvements on exhaustive search for NP-complete problems.

But this is where things begin to rub me the wrong way.  We certainly got an improvement, but we did nothing clever with our independent sets once we formulated the fact that they were useful to look for; we just did exhaustive search on them!  And there’s a sentiment I have that this isn’t really an improvement on exhaustive search since maybe the original exhaustive search for a 3-coloring was the wrong notion of exhaustive search and the right one was the independent set technique the entire time.  Or at least that exhaustive search isn’t well-defined since there’s a bunch of things we might be able to exhaustively search over to decide this problem.

And this is where the weird connection of search and decision comes in:  For a decision problem we just need to correctly say YES or NO regardless of how we get there.  And really the only way to get there is by going through some search problem and that will let us make that decision.  That is, to every decision problem there is a slew of corresponding search problems that decide it.

In fact, not only is exhaustive actually well-defined, it’s all there is!

That is, when we talk about improving exhaustive search, we really mean improving naïve search.  And what we do from there is find a different exhaustive search that is less naïve than the original one.

Find a smaller haystack.

So every decision problem is really a search problem.  A search for a witness as to whether we should decide YES.  The only trick is to cleverly swap out our big naïve haystack for a small one with a key property: there is a needle in the big naïve haystack if and only if there is one in the small haystack.

That way, we can just sift through a small (hopefully polynomially-sized) haystack with the confidence that what we find there will tell us what we would have found if we took the trouble to go through the giant one.

The real distinction isn’t between exhaustive search and something more clever, it’s between naïve search and all other types of (possible more clever) exhaustive search.  It’s all exhaustive search.

And all solutions to decision problems are just some form of haystack-swapping.

But this isn’t really a new idea.  It might be a nice framework to think in at times but the idea that everything boils down to exhaustive search was thought of before.  It even caused the Soviets to think the P vs. NP problem was solved (the part that was missed was that exhaustive may not be so bad if the haystacks we get down to are small) and caused a bunch of hoopla and controversy, especially when Leonid Levin defined NP-completeness.

Nonetheless, it’s haystacks all the way down.  And all decision problems come down to search problems (albeit, exhaustive search problems) for a witness.

But then what about search problems themselves?  Is it identical there?  Are there subtleties I’m leaving out?  And, most importantly, where is the disparity between decision and search problems I keep alluding to?

To be continued…

Advertisements
This entry was posted in Intermediate, Landscape, TCS and tagged , , , , . Bookmark the permalink.