Caleb Stanford Blog

Here are some facts about the four color theorem.

1. There is always a way to color the outer region as well.

Take a look at this 4-coloring of the US map, from the Wikipedia page:

It’s technically suboptimal because white is a color, too, and they used white for the outside! For some reason, this bothers me. It’s in fact always possible to color the entire map, including the outer region, with 4 colors. Here, I did it in Pinta image editor to show you:

(Note that Utah / New Mexico and Arizona / Colorado must be considered non-adjacent for the 4-color theorem to apply.)

2. The regions can have holes!

The 4-color theorem is valid even if not all of the regions are topologically disks; they can have holes. In fact, point #1 was already an example of this, since the outer region has one big hole. But it’s true more generally. However, the regions certainly can’t be “adjacent” to themselves, and also, they must be contiguous regions. Which brings us to:

3. The theorem doesn’t technically apply to real maps, including the US map.

Why not? Because real maps have countries and states that are split into multiple non-contiguous parts. In the US, that’s just the state of Michigan, but there are probably much worse examples world-wide. This blog post discusses it in detail and concludes that, as of July 2016, the globe still happens to be 4-colorable. (I guess that means 5-colorable if you include the color of oceans / water.)

Anyway I would def buy a globe that was 5-colored where blue is reserved for all bodies of water and countries which have multiple pieces are colored the same. That would be a cool thing to have.

Life goal: Don’t pull any more all-nighters for work.

Sleep has always been a sort of ongoing personal experiment for me. In high school I wanted to try out a 28-hour sleep schedule (see 1 2 3), but never succeeded. In college, I like to believe I perfected the art of staying up all night. Specifically, I mean staying up all night and then timing my bed-time perfectly to set myself in course for an earlier sleep schedule than I had before.

Yes, I was so tired getting up in the mornings that I found it easier — often much easier — to stay up all night (with plenty of food and caffeine, and other tactics) rather than have to go to bed and force myself awake in the morning. If this doesn’t strike you as absurd, it should! Of course, these all-nighters were often more or less forced by the work I had to do, but they were also usually exciting and energizing. I loved the novelty of doing a project or activity late into the night, until the sun rises and longer.

Since then, my tendency to stay up late has become more of a liability. I don’t feel energized to pull all-nighters the way I used to. But at the same time, I still find myself caught in late sleep schedules, unable to feel awake in the morning, and unable to power through a full all-nighter to reset things. Staying up for work has, as a result, become considerably more stressful and miserable.

This semester, I decided to see a doctor about my sleep patterns. Apparently I have Delayed Sleep Phase Disorder. The strategy for correcting (or just investigating) this starts by controlling for all possible negative influences (caffeine, inconsistent sleep, lack of association between bed and sleep, electronic screen time, and so on). In the absence of these factors, you try to obtain a “normal” 24-hour schedule, and you push wake-up time back slowly over a period of weeks. Finally, you start to experiment with which factors have the biggest effect by reintroducing them if necessary. Since classes are over and there are no deadlines, this is the perfect time to be working on sleep, and it’s an exciting project.

Perhaps in a few months I will be back to my usual patterns. That’s OK — it may be how I am happiest. Staying up all night for fun or with the right work drive can be really wonderful. But what I can’t do, and am not going to let myself do, is fail in planning my time so that staying up all night becomes the only possibility, instead of a decision. So, I’ve made that a life goal.

Unrelated: I’m going to write more posts.

I want to start writing in my blog more. I’m still a bit undecided on whether this is really a better idea than posting to Facebook. Especially since Facebook posts would probably get 10 to 100 times more views. But it’s a different kind of outlet, with different expectations and norms, and I want to try out using it consistently. I think it may have the possibility of being more free-form and more honest. When I post to Facebook I think too much about what my readers will think.

So my goal with the blog is to write down whatever I’ve been thinking about. And I also want to write more. I don’t want it to be polished, I just want to work on my writing and express my thoughts on things. Hopefully, by focusing on quantity instead of quality, I will start writing every week instead of every couple of months, and over time the quality will get better.

If you are familiar with theory of computation, perhaps you have caught yourself thinking of the relationship between NP and P as analogous to the relationship between RE and R. That is, nondeterministic polynomial-time is to polynomial-time as Turing-recognizable is to Turing-decidable. I certainly have thought this, and I think it’s because I visualize NP as a “positive” extension of P, with counterpart coNP, just as RE is a “positive” extension of R with counterpart coRE.

On the face of it, this rather seems like a misconception. NP is formed from P by introducing nondeterminism, whereas RE is formed from R by introducing non-halting behavior, and these are quite different concepts. In particular, if we add non-halting behavior to poly-time TMs, by requiring only that the TM runs in poly-time if it halts at all, we still only obtain the class of languages P. And on the other hand, non-deterministic TMs are equivalent to deterministic TMs (see e.g. Sipser 2nd edition, Theorem 3.16), so adding non-determinism to decider TMs we expect to remain at the class of languages R.

Nevertheless, this ignored StackOverflow answer claims a very close analogy in terms of verifiers, where just as NP is the class of languages with polynomial-time verifiers, RE is the class of languages which have verifiers at all. In fact this is true, but only if we allow the runtime of the verifier to be unbounded in the length of the original input, which seems like cheating considering that the runtime of a poly-time verifier must be uniformly bounded by a poly-time function in the length of the original input.

At the core of the problem is the definition of runtime and halting / non-halting for nondeterministic and verifier TMs. I summarize the discussion with the following table:

Given this, I think the correspondence between P : NP and R : RE is essentially a fluke, only present if we use verifiers rather than NTMs and if we only require that they halt, not that their runtime has a finite bound. The rest of this post just elaborates on and explains the above table.

Non-determinism and verifiers, in general

It is perhaps clearer to think of these concepts in the most general setting. Therefore, let us suppose that a model of computation begins with a collection of machines, a collection of possible inputs, and a collection of possible configurations. For any machine \(M\) and input \(w\), there is an initial configuration — e.g. for TMs it would be the tuple of the machine \(M\), the initial state \(q_0\), and the initial tape containing \(w\). Then we have a step function (or “small-step semantics”) which maps any configuration to a new configuration, taking one unit of time. Lastly there are some final configurations, which do not step. The evaluation of \(M\) on some input \(w\) (i.e., the “big-step semantics”) is the final configuration that is ultimately produced by a sequence of small-steps, if it exists. Moreover, let’s simplify this so that the output is binary, by saying that all final configurations either accept or reject.

A nondeterministic model of computation is the same but the small-step semantics can map a configuration to multiple possible configurations. In this case, \(M\) accepts input \(w\) if it is possible to arrive at an accepting configuration. (A discussion for another day is whether there are other reasonable definitions of the language of an NTM. Since there are many possible final configurations, we clearly need some way to aggregate all the configurations into one, and so it is natural to define some outputs to override others. In the standard definition we take accepting to override rejecting. But we could also take, for instance, non-halting behavior to override accepting!)

A verifier model of computation consists of an underlying model of computation, in which inputs are ordered pairs. A verifier machine \(\text{ver}(M)\) starts by mapping the input \(x\) to a new input \((x,w)\), where \(w\) is the witness, feeding that to \(M\). We formally say that \(\text{ver}(M)\) accepts \(x\) if there exists a witness \(w\) for which \(M\) accepts \((x,w)\).

Runtime bounds for non-deterministic and verifier TMs

To obtain \(NP\) from \(P\), we have to understand how to bound the runtime of a verifier (VTM) or nondeterministic TM (NTM) by a polynomial. In general, the runtime of a verifier or NTM must be a notion that does not depend on the particular branch executed, or the particular witness string.

If \(f(n)\) is some general function of \(n\), we can say that an NTM’s runtime is bounded by \(f(n)\) if, on any input of size \(n\), there is no branch with length longer than \(f(n)\) (including non-halting branches). A VTM’s runtime is bounded by \(f(n)\) if, on any input of size \(n\) and any witness, the runtime is bounded by \(f(n)\).

Using this definition, if we require \(f\) to be a polynomial, then NTMs and VTMs both give us NP. And then if we allow \(f\) to return any finite value (so, the runtime has to be bounded by a fixed function of the input), then both NTMs and VTMs give us R. The constant bound on the runtime means that we can simply try all possible branches or all possible witnesses with a deterministic TM, and that TM will always halt.

But the difference between NTMs and VTMs arises if we formally require the strict bound \(f(n) = \infty\). What this is saying is that all branches of the NTM are halting, and that the VTM halts on every input, witness pair. For NTMs, we can still simulate this with a deterministic TM, because if all branches of an NTM are halting, then we can try all of them and we will eventually halt. But for a VTM, we cannot try all witnesses, because there are infinitely many! It does not really matter that the VTM halts on each individual one. With a VTM, requiring the TM to always halt is no barrier to us checking a Turing-recognizable but not decidable property, because we get an existential quantification over all finite strings (an infinite set) for free.

So we can say that RE is the set of languages recognized by a verifier TM which always halts. But this is somewhat dubious because maybe the “right” definition of the runtime of a verifier TM is the supremum over all witnesses, in which case a verifier for a language in RE but not in R will have runtime \(\infty\). And maybe the right definition of a halting verifier is one whose runtime is finite. Under this definition, the subtle difference between NTMs and VTMs, highlighted in the original table, would disappear.

References

My definition of a decider / halting NTM does agree with Sipser 2nd edition, page 152, where he requires that a decider NTM halt on all branches. Sipser page 255 only defines the runtime for decider NTMs. This CS StackExchange thread also gives several different definitions of a nondeterministic decider, which are all equivalent and recognize R. As for verifiers, on Sipser page 265 it is suggested (but only really for the polynomial case) that the runtime for verifiers should be the supremum over all witnesses.

In descriptive complexity, Fagin’s theorem shows that NP arises from P essentially by allowing existentially-quantified second-order variables. On the other hand, RE arises from R by allowing existential quantification over \(\mathbb{N}\).

This old CS StackExchange question seems to me a great question which is asking what I asked, but its answer does not really say anything. This post in hebrew might be mildly relevant but I can’t read it.