Talkin' bout magical computers
Immerman's theorem, named for Neil Immerman, whom I took a course with once, states that NL = co-NL. The fuck's that mean?
Well, say you have a magical computer and a budget airline; say if you wait long enough, two cities are directly connected or they're not, but two cities being connected doesn't mean the return trip is connected. The computer, like I said, is magic: if you give it a yes/no question, you can tell it to take a guess, and as long as it's possible, the computer will always give a series of answers that lead to "yes." Now, let's say you want to see whether your cheap-ass airline can get from A to B in any number of layovers.
First, you give the computer A. You tell it to guess a destination. If you can't fly there directly, you tell it to answer "no." (Remember, it doesn't want to answer "no.") If you can fly there directly, and it's B, answer "yes." If you can fly there directly, and it's not B, increment a counter; if the counter is the number of cities you serve, answer "no," and if not, make this your new A.
You'll note that the computer at any one time only stores a starting city, a target city, and a count of the number of cities you have. You can put all of these down as indices of cities, so the space you need is proportional to the number of bits in the number of cities, i.e., the digits you need to write down how many cities you serve. In a word, you need logarithmic space. That's NL.
In fact, any problem in NL can be modeled as such a problem, since if a computer's memory is restricted to a constant multiple of the number of bits in the input, you can consider a "city" to be the entirety of the possible states of the memory, plus the position in the code of the algorithm, and the magic "guess" operator is accounted for by the fact that planes can go to multiple cities. So the number of bits in the number of cities will just be the number of bits you needed before, plus a constant for the code, which is still within a constant multiple of the bits in the input for sufficiently large input.
Okay, so it'll magically guess the values that bring it to a "yes," if there is one. But what if it's the opposite? What if the magical computer wants at every turn to bring you to a "no"? Well, you should ask the opposite question - show there isn't a path. That's co-NL, and the fact that it's possible to show there isn't a path is Immerman's theorem.
Basically, if you can show that you can't get there in so many steps, by putting in as the number of steps the number of cities, you can get there. So for one step, you can just run through all the cities and see that you can't get there from the starts. Since you can do that, you can also check (and store, since its value is less than the number of cities) how many cities you can't get to in one step. For any other number of steps, assuming that you know how to check and store how many can't get there in one step fewer, you can check by checking for each city how many can be reached from one step fewer, then running through each city other than the current, finding a path there (as before, only switching "no" with "yes"), adding one to a count of those points reached, and if the first city can be reached from the second, moving on to the next, incrementing a count, otherwise going back until you're out of cities to find the first from. At this point, you check if the count of cities reached in one less step is the count expected; if not, you say "yes" (which the computer doesn't want). You keep going until you're through all the cities, and if the cities are all the cities, well, you can't get theah from heah.
All right, so let's go on to the more famous one (which I hadn't been planning to do until I chose my title). Cook's theorem started the ball rolling on the question you've probably heard of, whether P = NP. What that means is whether there's anything that magical computer can do in polynomial time (i.e., a length of time that increases in proportion to a constant power of the length of the input) that an ordinary computer can't (not necessarily the same power between the two). Cook's theorem states that if you can, with an ordinary computer, say whether a gaggle of ands, ors, boolean variables, and parentheses has a possible assignation to those variables that yields "true" for the whole gaggle, that magical computer can't do more than an ordinary one. Very quickly about a thousand things (at least twenty-one) were shown to be easy stepping-stones to solve this, and therefore only doable if the magical computer weren't so magical after all. The most famous of these is the "travelling salesman problem," going back to that airline, what's the shortest possible way to get to every city exactly once and back to where you started? This is because it would allow you to determine whether a graph has a Hamiltonian cycle, that is to say, any way to get to every city exactly once and back, and from that you could figure out the smallest number of cities that together are one edge or the other of every flight path, by... uh... hmm.
Okay, this is going to need its own paragraph. You're checking whether there's a subset of vertices that touches every edge (that is, cities from which... fuck it, it means vertices that touch every edge) less than some input number. What you have to do is make from the graph you start with a graph that'll have a Hamiltonian cycle if and only if the graph you started with had a vertex cover less than that size. Well, the vertices of that graph, you'll have one vertex for the allowable number of covers, plus two sets of vertices for each adjacent pair of edge and vertex in the original graph. As for the edges, first, there's always a one-way edge between the corresponding vertices there from the first set to the second. Within each set (but not between sets), there's a two-way edge between any two vertices whose pairs had the same edge on the original graph. There's a one-way edge from the second set back to the first between vertices representing edges adjacent to the same vertex on the original graph SO LONG AS in between the ordinals of the edges on the original graph (i.e., numbers assigned arbitrarily just to tell them apart) there isn't another edge that touches that vertex. There's also a one-way line from the vertex in the second set that represents the highest-numbered edge that touched a given vertex on the original graph to all of those special vertices mentioned at the beginning, and from all of those special vertices to the vertex in the first set that represents the lowest-numbered edge that touches a given vertex. This works because Karp says so.
So if you can compute the travelling salesman problem, you can find a directed Hamiltonian cycle, and from there you can find whether there exists a vertex cover below a given size. And from there? Well, if you look at the sketched proof up there, the formula you get from it can always be made into a single "and" of "ors." (Both of which may have unbounded fan-in, i.e., to use the natural language analogue, a shitload of clauses.) So you draw up a graph where the vertices are labelled with ordered pairs of variables (counting each and its complement separately) and the clauses in which they occur. Put an edge (either or both directions, it doesn't matter because of the nature of the vertex cover problem) between them if one is the negation of the other or if they're in the same clause. The number we're shooting for is the number of vertices minus the number of clauses. If it's satisfiable, you can pick a vertex for each clause that's not part of the vertex cover and that'll do ya. If not, either you're going to have to take out one and its own negation, or you're going to have to take out a whole clause. If, and only if.
So that's the concept of "NP-completeness," which you'll hear sometimes used to mean, essentially, "wicked hard"; that's sort of Cobham's thesis, which is that P is roughly what's tractable, and since NP-complete problems aren't thought to be in P, there's the story. This brings up the notion of Anathem, in which the "travelling fraa problem" is solved by a "Saunt Grod's machine," which uses quantum effects. Now, it's not certain that this is a slightly-less-imaginary quantum computer, but assuming it is, again, there's no proof that a quantum computer could solve NP-complete problems, and Fraa Jad really doubles down by saying that he finds a code by picking numbers randomly.
...I guess I don't really have much else to say, although I feel I should mention Savitch's theorem, that if you have one of these imaginary computers, and you've programmed it to do something with only so much memory, if time is no object, you can get a more realistic computer to do it with (proportional in terms of the input to) the square of the memory. Basically, you dig down all the possible states from either end. Anyway, I'm posting this.
