How do you get a "Physical Intuition" for results in TCS?

Question

I'm sorry if this question is a little vague, but I am curious how successful researchers get a "feel" for the results in TCS.

For example, linear algebra can be understood geometrically, or in terms of its physical interpretations (eigenvectors can be thought of as "stable points" in a system), etc. It's also intuitive that there exists an IP protocol for TQBF (as the IP protocol can be visualized as a kind of a "game" between two entities of greatly differing computational power). However, I find that a lot of the results, even extremely basic ones in TCS do not have such simple intuitions (MA $\subseteq$ AM). Worse still, occasionally, unrefined intuitions go awfully wary (2-SAT is in P while 3-SAT is not believed to be in P (in fact, is NP-complete)). Are there any "general principles" for developing an intuition in TCS?

Answer 1

Like many scientific fields, it can take years to build intuition, but it can take only one new idea to tear that intuition down (and hopefully something nice gets rebuilt in its place).

There are some basic exercises you can use to try to build intuition for some paper you're reading and can't seem to penetrate. Here's one that I still do from time to time. Start with a proof that you don't understand but would really like to, which is very long. As you read each paragraph of the proof, try to write a sentence in your own words about what you think the paragraph is saying, in the margins. Hopefully the proof is written well enough that there are well-defined "parts" to the proof ("do X, then define a new function f, then apply X to f, ..."). If not, then from your sentences, separate the proof into your own parts.

Now for each part, try to write a sentence (in your own words) about what each part is doing. At this point, it could be that you find your earlier sentences are not quite accurate or don't fit well together (your intuition was "off"), so you may refine them so they fit logically together. Now you have a few sentences summarizing the whole proof. Then (now this last part is from my advisor, Manuel Blum) try to think of one word or phrase for the whole thing. This phrase would be the key idea that, in your mind, is what gets the whole argument started. (For example, most existence proofs via the probabilistic method can be summed up by: "PICK RANDOM". In the case of $MA \subseteq AM$, I would say something like "MAKE ARTHUR SPEAK MORE". But maybe something else in the proof feels to be the "key" idea to you, which is perfectly fine. It's your intuition!)

I guess my suggestion may be useful for most mathematics, but I found it very useful for TCS, where many proofs really do boil down to 1-2 really new ideas, and the rest is a synthesis of that idea with what was already known.

Answer 2

Be careful about intuition. It comes with a great deal of experience, can often be wrong and right at the same time, and is not unique. The point is that everyone brings their own intuition to problems based on their own comfort zones, the needs of the problem, and their background. As Tsuyoshi points out, intuition is really a lot of hard work that's been sublimated into a few concise mental images.

So my suggestion would be: just work on problems you enjoy, and try to develop your own ideas even if there's other work out there. You'll build intuition that way. And if a result seems puzzling, it either means you haven't quite understood it yet, or maybe there's a simpler result lurking somewhere beneath, waiting to be uncovered.

Answer 3

Since you count games as an example of “physical intuition” while I cannot see anything related to physics in games, I assume that your emphasis is not on “physical” but on “intuition.”

I argue that part of the purpose of study (education or research) in theoretical computer science is to develop the intuition for the abstract notions related to computation. Intuition is acquired by studying and getting familiar with the concept. I do not expect that there is a nice shortcut.

For example, undergraduate students will be surprised by undecidability of halting problem (probably because the mere existence of an undecidable language is already surprising). But learning the fact, its proof, some related results and the wide applicability of the proof technique makes this surprising result less surprising and in fact very natural. I believe that the same is true for more complicated results.

As for the specific result, I do not agree that there is no simple intuition for MA⊆AM. (Warning: I am currently studying this and related results myself, and I may say something incorrect.) In an MA system, Merlin has to give a single answer which fits most of the random sequences used by Arthur. We change the system so that Arthur sends several (polynomially many) random sequences to Merlin and Merlin has to give a single answer which fits all of them, which seems to me like a natural thing to try. Proving the soundness of this AM system is a simple application of the Chernoff bound. I do not think that anything in this result is conceptually difficult to understand.

Marginally related: Your question reminded me of a beautiful blog post “Abstraction, intuition, and the ‘monad tutorial fallacy’” by Brent Yorgey, where he explained the difficulty of communicating the intuition by a fictional non-explanation “Monads are Burritos.” If the above explanation of how the proof of MA⊆AM works does not make any sense, I might be demonstrating the same fallacy. :(

Answer 4

If you spend five years of your life by studying a purely theoretical concept X (e.g., a certain esoteric model of computation), then eventually X becomes a natural part of your daily life.

You will learn to know how X behaves, what it feels like, how it responds to your manipulations, and in what kind of neighbourhood it lives. You will learn who discovered it, when, and why, and what others have done with X, successfully or unsuccessfully. You will know X just like you know any physical object that you encounter every day.

Indeed, you may know it much better than those strange, ill-defined, unpredictable, and erratic physical things... But it is a long way, and I don't think there are that many magic shortcuts.

Answer 5

The answers here already cover most of the nice suggestions about intuition. Still I would give it one more, which is usful when developing intuitions during paper writing. This is suggested by my own teacher, Hsueh-I Lu, which I found it very useful.

Whenever a result is written down, and the correctness seems to be verified, rewrite the whole article. This time we have to enforce ourselves not to use any words or definitions similar to the previous versions. This makes us think in a completely new different way, and new intuitions will develop. Also, perturb every parameters used in the paper, see if any set of parameters differ from the one we used originally works still. Often some mistakes exposed when rewriting the article. Come up with new ideas to overcome them.

Finally, after rounds of rewriting, we will have a nice round intuition about our own result, and we won't be too optimistic/pessimistic to the power of the new ideas presented in the paper, since we're tried for a couple of times, and it is clear that what is working and what is not.

The same method works if you are reading a new paper, and wants to get some more intuitions other than the one given by reading.

Answer 6

In my own case, most TCS concepts I feel like I have any intuition about are those I backed into via practical results. If I find myself evolving and using the same model or algorithm successfully for years, it tends to increasingly drive me to distraction until I can figure out why the algorithm's been successful. This is particularly true if it's time for a rewrite -- I want to know what the TCS essence of the thing is, lest I lose the magic dust while refactoring. Figuring all of that out usually requires (for me) a deep dive back to 1936 or so, and relating what I've been doing with those basic concepts. A friend once advised me to "think like a turing machine" when I was on one of those dives, and that advice has stuck with me.