10 • Problem solving and combinatorial explosion
Rationality involves more than just being logical. Is a capability for insight what differentiates us from machines?
But many problems we face are not at all clearly defined, they are ambiguous. A logical proof of certainty for those is beyond our capabilities, beyond our understanding of those problems.
Today I want to dig deeper into what exactly makes deductive reasoning and logical proofs often challenging and inaccessible to us, when we are trying to solve real-world problems.
Algorithms
What's an algorithm? An algorithm is a problem solving technique that is guaranteed to find a solution or prove — and I'm using that term technically, not “give evidence for” but prove — that a solution cannot be found. And of course there are algorithmic things you do: You know the algorithm for doing multiplication, for example, 33 times 4. There is a way to do that in which you can reliably guarantee to get an answer.
This is important, and I remember I said I'd come back to you and explain why Descartes' project was doomed for failure? Because algorithmic processing is processing that is held to the standard of certainty. You use an algorithm when you are pursuing certainty.
Now what's the problem with using an algorithm as a problem solving technique? Well, it's guaranteed to find an answer or prove that an answer is not findable. So algorithms work in terms of certainty.
Ask yourself: in order to be certain that you found the answer or prove that an answer cannot be found, how much of the problem space do you have to search?
There's some a priori things you can do to shave the problem space down a little bit, and computer science talks about that. But generally, for all practical purposes and intents, in order to guarantee certainty, I have to search the space, the whole space, and the space is combinatorially explosive.
So if I pursue algorithmic certainty, I will not solve any problems. I will have committed cognitive suicide. If I try and be algorithmically certain in all of my processing, if I'm pursuing certainty, as I'm trying to get over to the cup, a combinatorially explosive space opens up and I can't get there because my lifetime, my resources, my processing power is not sufficient to search the whole space.
That's why Descartes was doomed from the beginning. You can't turn yourself into Mr. Spock. You can't turn yourself into Data. You can't turn yourself into an algorithmic machine that is pursuing certainty. That is cognitive suicide.
That tells us something right away, by the way, because logic — deductive logic — is certainty. It is algorithmic. It works in terms of certainty. An argument is valid if it is impossible for the premises to be true and the conclusion false. Logic works in terms of the normativity of certainty. It operates algorithmically. So does math.
You cannot be comprehensively logical: If I tried to be Mr. Spock and logic my way through anything I'm trying to do, most of my problems are combinatorially explosive and I won't solve even one of them because I'd be overwhelmed by a combinatorially explosive search space.
Being rational ⊃ being logical
This tells you something. This is what I meant earlier when I said trying to equate rationality with being logical is absurd. You can't do that. The issue: these terms are not, and cannot be — as much as Descartes wanted them to be — they are not, and cannot be synonymous.
Now that doesn't mean that rational means being illogical or willy-nilly. […] “Ratio”, “rationing”, “being rational” means knowing when, where, how much, and to what degree to be logical. And that's a much more difficult thing to do.
And I would argue more that being rational is not just the psycho-technology of logic, but other psycho-technologies, knowing where, when, and how to use them, in order to overcome self-deception and optimally achieve the goals that we want to achieve.
Often when they talk about rationality, people think I'm talking about logic or consistency and they misunderstand that is not what I've meant. And that's what I said when Descartes was wrong, in a deep sense, from the beginning.
Rationality involves being able to apply the psycho-technology of deductive reasoning, but logic alone is not sufficient for rationality. To avoid combinatorially explosion, we have to employ other problem solving strategies and leave certainty behind.
Heuristics
A heuristic is a problem solving method that is not guaranteed to find a solution. It is only reliable for increasing your chances of achieving your goal.
I've just shown you: you cannot play chess algorithmically. Of course you can — and even the best computer programs do this — play chess heuristically. You can play chess doing the following things; here are some heuristics: “get your queen out early”, “control the center board”, “castle your king”. You can do all of these things and nevertheless not achieve your goal — winning the game of chess. And that's precisely because of how heuristics work.
What heuristics do is they try to pre-specify where you should search for the relevant information. That's what a heuristic does: it limits the space you're searching. Now, what that actually means is it's getting you to prejudge what's going to be relevant, and of course that's where we get our word prejudice from. A heuristic is therefore a bias, it's a source of bias. This is why the two are often paired together — the heuristic-bias approach.
What my chess heuristics do is they bias where I'm paying attention. I focus on the center board, I focus on my queen. If I'm playing against somebody who's very good, they'll notice how I'm fixated on the center board and the queen, and they'll keep me focused there while playing a peripheral game that defeats me. […]
This is called the No Free Lunch Theorem: that it is unavoidable — you have to use heuristics because you have to avoid combinatorial explosion. You can't be comprehensively algorithmic, logical, mathematical. The price you pay for avoiding combinatorial explosion is you fall prey to bias. […] The very things that make us adaptive are the things that make us prone to self-deception.
We can avoid combinatorial explosion with heuristics, but we also have to give up certainty and we are not guaranteed to solve the problem. Why would we want to do that? Because most real-world problems do not come structured in a way to be solved algorithmically.
Well- and ill-defined problems
Well-defined problems
In a well-defined problem I have a good meaning and effective guiding representation of the initial state, the goal state, the operators, so that I can solve my problem. I take it that for many of you that problem I gave earlier [33 x 4] — and there is a relationship between something being well-defined and algorithmic; they are not identical, but there is a relationship — for many of you that should be a well-defined problem:
You can tell me your initial state: this is a multiplication problem. And that gives you useful guiding information. You know a lot of things by knowing your initial state.
You know what the goal state should look like: This should be a number when I'm done. And you know that this number [the result] should be bigger than these two numbers. The most beautiful picture of all time of a platypus does not count as an answer.
You know what the operations are: singing and dancing are irrelevant to this.
A lot of your education was getting you to practice making whole sets of problems well-defined. And part of what psycho-technologies do is they make well-defined problems for us, like literacy, and numeracy, mathematics. And because of that power and because of their prevalence in our education, we tend to get blinded, and we tend to think that that's what most problems are like. And that means we don't pay attention to how we formulate the problem, because the problem is well-formulated for us precisely because it's a well-defined problem.
[continued below]
With programming, we solve well-defined problems:
We have an initial state: we know the types of the input, and we will know the exact input at runtime.
We have a goal state: we know the type of the output, and we will know the exact result (the inhabitant of that type) after running our operations on the initial state (or we will discover that the computation takes too long).
We have the operations: we know (or we come up with) a series of operations that are at least well-defined in the sense that the computer knows how to execute them.
This is practically the definition of a function in pretty much any programming language.
[continued from above]
Ill-defined problems
But most of your problems are ill-defined problems. In most of your problems, you don't know what the relevant information about the initial state is. You don't know what the relevant information about the goal state is. You don't know what the relevant operators are. You don't even know what the relevant path constraints are.
You're sitting in lecture, perhaps at the university, and you've got this problem: take good notes.
“Ok, what's the initial state?”
“Well, I don't have good notes.”
“And?”
“Uh, well, um, yeah. Ok… ok.”
“What should I do?” And all you do is give me synonyms for relevance realization:
“I should pay attention to the relevant information, the crucial information, the important information.”
“How do you do that?”
“Uh, well, you know, it's obvious to me, or it stands out to me!”
“Great, but how? How would I make a machine be able to do that?”
“…?”
“What are the operations?”
“Oh, I write stuff down.”
“Do you? Do I just write stuff down? Like, I draw, I make arrows. Do I write everything down?”
“Well, no, I don't write everything down and I don't just…”
“What are the operations?” Does that mean everybody's notes will look the same? No, when I do this in class everybody's notes look remarkably very different. “So what are the operations and what does the goal state look like?”
“Well, good notes.”
“Great! What are the properties of good notes?”
“Well, they're useful.”
“Why are they useful?”
“Well, because… oh, because they contain the relevant information connected in the relevant way that makes sense to me. And so that I can use it to… yeah, right… I get it.”
What's actually missing in an ill-defined problem is how to formulate the problem, how to zero in on the relevant information and thereby constrain the problem so you can solve it. What's missing and what's needed to deal with your ill-defined problems and turn them into something like well-defined problems for you is good problem formulation, which involves this process of zeroing in on relevant information — relevance realization. […]
So we already see that the relevance realization that's at work in problem formulation is crucial for dealing with real world problems. Taking good notes — that's an ill-defined problem. Following a conversation — that's another ill-defined problem.
“Well, I should say things.”
“What things?”
“Well, oh…”
“When?”
“Well, when it's appropriate.”
“How often?”
“Well, sort of…”
Tell a joke. Go on a successful first date. All of these are ill-defined problems. Most of your real world problems are ill-defined problems. So you need the relevance realization within good problem formulation to help you deal with most real world problems. Already, problem formulation is crucial.
Many important problems we face require us to figure out what exactly the problem is in the first place. Only with a good enough problem formulation can we attempt to find a solution.
If we manage to specify the problem precise enough, we can attempt its solution algorithmically, but we may not be able to solve it, if it is combinatorially explosive. However, sometimes all that is needed is a different perspective, to change a solution strategy that is combinatorially explosive into one which has an obvious solution.
Changing perspective
This is called “The Mutilated Chess Board” example. There are eight columns and eight rows. And so we know that there are 64 squares. Now, because this is a square […], if I have a domino and it covers two squares, it'll cover two squares equally if I put it horizontally or vertically. How many dominoes do I need to cover the chess board?
Well, that's easy, 2 goes into 64 — I need 32. 32 dominoes will cover this without overhang or overlap.
Now I'm going to mutilate the chess board. I'm going to remove this [bottom-left corner] piece and this [top-right corner] piece. How many squares are left here? 62. There are 62 squares left. So I've now mutilated the chess board.
Here's the problem: Can I cover this with 31 Domino's without overhang or overlap? And you have to be able to prove — deductively demonstrate — that your answer is correct.
Covering strategy
Many people find this a hard problem. They find it a hard problem — perhaps you're doing this now — because they formulate it as a covering problem. They're trying to imagine a chess board and they're trying to imagine possible configurations of dominoes on the board. So they adopt a covering formulation of the problem, a covering strategy, and they try to imagine it. That strategy is combinatorially explosive.
So famously there was somebody, one of the people in one of the experiments, one of the participants, trained in mathematics and was doing this topographical calculation and they worked on it for 16 to 18 hours and filled 81 pages of a notebook. And they didn't come up with a solution. Why? Because if you formulate this as a covering strategy, you hit combinatorial explosion. The problem space explodes and you can't move through it. And that's what happened to that participant. It's not because they lacked the logic or mathematical abilities. In fact, it was precisely because of their logic and mathematical abilities that they came to grief.
Now, you should know by now that I am not advocating for romanticism. “Oh, just give up logic and rationality.” That's ridiculous! You've seen why I'm critical of that as well. But what I'm trying to show you is: you cannot be comprehensively algorithmic.
Reformulation: parity strategy
If you formulate this as a covering strategy, you can't solve it. Let's reformulate it. […] These [taken out] squares are always the same color on a chess board. In fact, that's not hidden in the diagram and what's used in the actual experiment — that's clearly visible — these squares are always the same color.
You say, “so what?”
Right. That's the point!
You can see them, but they're not salient to you in a way that makes a solution obvious to you. They’re not salient to you. They're there, but they're not standing out to you in a way that makes a solution obvious to you.
Let's try this: If I put this domino on the board, if I put it horizontally or vertically, I will always cover a black and white square. Always. There is no way of putting it on the board that will not cover a black and white square. So in order to cover the board with dominoes, I need an equal number of black and white squares. I must have an equal number of black and white squares. That must be the case. But these [two taken out] squares are the same color! Is there now an equal number of black and white squares there? No. Because these [removed ones] are the same color. There's not an equal number of black and white squares.
I must have an equal number of black and white squares. I know for sure — because these [two removed ones] are the same color — I do not have an equal number of black and white squares. Therefore I can prove to you that it is impossible to cover the board with the dominoes.
If I go from formulating this problem as a covering strategy, which is combinatorially explosive, to using a parity strategy in which the fact that [the two removed squares] are the same color is salient to me, such that now a solution is obvious — now, it's obvious that it's impossible — I go from not being able to solve the problem because it's combinatorially explosive to a search space that collapses and I solved the problem.
Insight
This is why the phenomenon we've been talking about when we talked about flow and different aspects of higher states of consciousness is so relevant. This capacity to come up with good problem formulation — problem formulation that turns ill-defined problems into well-defined problems for you; problem formulation that goes from a self-defeating strategy because of combinatorial explosion to a problem formulation that allows you to solve your problem — that's insight. That's insight. That's why the title of this experiment is “In Search of Insight”. That's exactly what insight is. It is the process by which bad problem formulation is being converted into good problem formulation.
That's why insight, in addition to logic, is central to rationality. And in addition to any logical techniques that improve my inference, I have to have other kinds of psycho-technologies that improve my capacity for insight. And we've already seen that that might have to do with things like mindfulness — because of mindfulness’ capacity to give you the ability to restructure your salience landscape.
So we're starting to see how problem formulation and Relevance Realization are actually central to what it is for you being a real-world problem solver: avoiding combinatorial explosions, avoiding ill-definedness.
A change of perspective can cause insight. At first we’re not able to pick out the relevant information that is already there, clearly noticeable. But then, a sudden flash of insight reconfigures our salience landscape such that a solution becomes obvious.
Computers can algorithmically calculate solutions to well-defined problems for us. We have yet to figure out how they can generate insight into ill-defined problems.
What if computers don’t need to have insights themselves (and become conscious in the process)? What if we don’t have to solve the difficult problem of artificial general intelligence first? What if computers could merely generate useful alternative perspectives that we humans can then switch between effortlessly, so that they can cause insights in us?
This is what I believe a tool (or medium) for thought should be.
If you are new to this series, start here: A secular definition of sacredness