Complexity is determined by calculating the upper and lower bounds for the number of steps (the TIME, capitalized for a reason) and/or the amount of memory (the SPACE) needed by a computer to process a solution and generate an output, given some body of data that is taken in as input. To keep things “simple” – <awkward throat clearing sounds here> – a very basic model of a computer is chosen, typically our old friend the Turing machine. (You remember them, right? I talked about them a bit HERE and HERE.) Turing machines are shockingly basic – they make your grandparents’ (or, if you’re young enough, Great Grandparents’) clunky old gear and levers mechanical adding machine look like a Spectacular Miracle of the Modern World. And yet, as grotesquely simple as a Turing machine would be in physical realization, it is still capable of performing all of the operations of your smart phone, tablet, laptop, or gaming console is capable of. It just takes longer.

But that longer can be calculated – not exactly, but to a meaningful worst case upper bound – by a simple type of formula, called a polynomial equation. Polynomial equations can generate really big numbers, of course; but ultimately they are just numbers, and they are generated through the same basic arithmetical operations you were exposed to (notice how careful I was not to say “learned”) in grade school. Let’s call the class of problems that can be solved by a Turing machine with “only” a polynomial degree of difficulty “P”.

There is a class of problems that seem to resist P levels of solution. (You probably guessed that much from the fact that I bothered to mention P in the first place.) We don’t know how to solve such complex problems, but we do know how to verify that we have a solution – provided we have one! However, even that verification is a bit tricky, and we need something a little more advanced than an ordinary Turing machine which makes all of its moves in a purely deterministic way (just as all computers do.) We need a non-deterministic Turing machine – there is absolutely no clue if such a thing is even physically possible, but these are mathematical considerations – which can then verify our proposed solution in non-deterministic polynomial TIME &or SPACE resources. It should come as no surprise that this class of problems are designated as “NP.” Notice that P and NP address somewhat different issues; the first is about generating a solution from the ground up, while the second is about generating a verification once a proposed solution is in hand. P is based upon known physical possibilities, while NP makes no such presupposition. (However, if quantum computing can be made generally feasible,ⁱⁱⁱ then it might provide such a physical foundation.)

The big question in complexity theory it this: does P = NP, or are these two classes irreducibly different from one another? Is it the case that P ≠ NP?^iv Scientists working in the field are overwhelmingly convinced that P ≠ NP is the case. For all of our sake’s, I sincerely hope so (I’ll say more in a moment.) In any event, despite great efforts being directed to the puzzle, no proof either way is yet to be had.

In my earlier posts on complexity, I mentioned the mathematical idea of an “oracle.”^v This is a pure piece of formal phlebotinum in which “and then a miracle happens” is formally recognized as a step in the process. In this case, a computing device can ask a question (even one that is otherwise unanswerable) of the oracle, “and then a miracle happens” and the question is answered. Again, no proposal is offered for how one might physically realize such an oracle (especially since it is physically impossible!) This is just a mathematical rabbit being pulled out of a mathematical hat to see what happens when we add it to the equation. But it is not an absolutely promiscuous, unlimited miracle; one must still maintain some semblance of a mathematically interesting puzzle. For one thing, the oracle cannot ex fiat legislate answers to other problems. And that being the case, it turns out that even with an oracle (or any number of them) one cannot resolve the question of whether or not P ≠ NP is the case.

There are a variety of additional complexity classes to just and only these basic ones. Some look specifically at polynomial degrees of complexity that focus exclusively on the amount of memory space a computer consumes to run a program on given inputs. This would be the PSPACE class of problems (recall the all capitalized terms above.) There is the non-deterministic study of time focused problems (NTIME), and problem classes studying exponential (EXP) levels of complexity. Working out how all these classes relate to one another, and setting better and better upper and lower bounds for what can and cannot be done (recall, these studies look at worst/best case scenarios of classes of problems rather than individual puzzles on specific inputs) constitutes the study of computational complexity.

Finally, a word on why you really, really wantto actually be the case.

Everything runs on the internet now. And I don’t just mean your shopping and streaming videos. The gas, electricity, and water that come to your home are all controlled via – ideally secure – connections on the internet. All of your personal and medical records are accessed via – ideally secure – connections on the internet. All of your financial transactions, your banking records, your credit rating, all of it, is accessed via – ideally secure – connections on the internet. Recall the chaos from earlier this year when hackers shut down gas supply up and down the eastern US seaboard? Well, that happened because the ideally “secure” internet connection was not. It could have been; it certainly should have been. But imagine the scenario where that connection could not possibly have been secure under any circumstances. That is the world in which P ≠ NP turns out to be false, or is rendered irrelevant by genuinely effective programmable quantum computing. This is not a trivial matter.

– – – – – – – – – –

i These last two are the recursively enumerable and the recursive problems respectively. I’ll not be pursuing this subject at all, in part because it is even more crazy difficult than the stuff I am going to talk about. Bearing in mind that this stuff is really dense, even at an intro level, the curious might do well to look at Martin Davis’ works HERE and HERE.

ii Basically, God could solve an intractably difficult but solvable problem. But not even God could solve an inherently unsolvable problem (except by cheating.)

iii Google’s claims about quantum computing are generally devoid of any real credibility as far as generalized programmable computing is concerned. Their machinery, insofar as it is real at all, is only capable of computing one problem and then it is effectively destroyed. And none of their claims have been subjected to real peer-review, since they don’t want to reveal any of their “proprietary information” regarding their hardware. So their position is, “Trust us! We’re making spectacular progress! (But you can’t see it.)”

iv For fans of the TV program Numb3rs – and if you’re not, why aren’t you? – whenever the mathematician brother, the character Charlie Eppes (played by David Krumholtz) got seriously stressed out, his retreat was to work on the problem of P ≠ NP.

v Once again, this is the classic “Sid Harris step #2” cartoon.