<p>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).</p>

<p>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 <strong>in your own words</strong> 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. </p>

<p>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 <strong>one word or phrase</strong> 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 <em>your</em> intuition!) </p>

<p>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.</p>

CC BY-SA 2.5
2011-02-09T08:29:56.377Z
Wonderful answer.
Anthony Labarre
CC BY-SA 2.5
2011-02-10T07:09:59.280Z
Let me add one suggestion to Ryan's great answer.  If at some point you get stuck reading someone else's proof, PUT IT DOWN and try to prove the result yourself.  Your belief that the result is probably true (otherwise why would you be reading the paper?) makes it much easier to come up with your own proof.  If you fail, the effort will build up your intuition.  If you succeed, your proof may be VERY different than the proof in the paper you're reading, in which case you have  intuition that the author does not!  I can credit at least three or my papers directly to this trick.
Jeffε
CC BY-SA 2.5
2011-02-09T01:00:54.213Z
2011-02-09T01:00:54.213Z
Ryan Williams
<p>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. </p>

<p>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. </p>

CC BY-SA 2.5
2011-02-08T21:36:02.457Z
2011-02-08T21:36:02.457Z
Suresh Venkat
<p>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.”</p>

<p>I argue that part of the purpose of study (education or research) in theoretical computer science <em>is</em> 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.</p>

<p>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.</p>

<p>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.</p>

<p>Marginally related: Your question reminded me of a beautiful blog post “<a href="http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/" rel="nofollow">Abstraction, intuition, and the ‘monad tutorial fallacy’</a>” 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. :(</p>

CC BY-SA 2.5
2011-02-08T22:20:30.960Z
There are undergrads who find undecidability surprising? Do they not teach them about Gödel first?
Peter Taylor
CC BY-SA 2.5
2011-02-08T22:24:02.867Z
I certainly didn't get Gödel in my undergrad CS education. In fact, I didn't get Gödel as an undergrad at all. (This was at an EECS dept., mind you, but nonetheless)...
sclv
CC BY-SA 2.5
2011-02-08T22:38:36.873Z
Given what I know about monads, they might as well be burritos ;)
Suresh Venkat
CC BY-SA 2.5
2011-02-08T22:47:10.477Z
Oh man I miss Floridian burritos, Do they send them delivery overseas? :)
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-09T09:17:25.740Z
@Suresh: I suspect the most useful analogy for you might be "Moore closures are to posets as monads are to categories". You can get awfully far in category theory by treating categories as lattices with multiple ways for one element to be below another.
Neel Krishnaswami
CC BY-SA 2.5
2011-02-08T21:33:18.157Z
2011-02-08T22:01:40.770Z
2011-02-08T22:01:40.770Z
Tsuyoshi Ito
<p>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.</p>

<p>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.</p>

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

CC BY-SA 2.5
2011-02-08T22:58:53.017Z
2011-02-08T22:58:53.017Z
Jukka Suomela
<p>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.</p>

<p>Whenever a result is written down, and the correctness seems to be verified, <strong>rewrite the whole article</strong>. This time we have to enforce ourselves <em>not</em> 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, <strong>perturb every parameters</strong> 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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-02-09T01:41:54.307Z
2011-02-09T01:41:54.307Z
Hsien-Chih Chang 張顯之
<p>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 <em>why</em> 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.</p>

CC BY-SA 3.0
2012-03-31T02:27:25.053Z
2012-03-31T03:25:20.210Z
2012-03-31T03:25:20.210Z
stevegt
<p>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.</p>

<p>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? </p>

CC BY-SA 2.5
2011-02-08T20:47:57.967Z
Please do spell-check next time you post.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T20:52:51.727Z
sorry :( will do
gabgoh
CC BY-SA 2.5
2011-02-08T21:35:53.287Z
A message from the NP-completeness police: proving that 3SAT is in NP does not imply the difficulty of 3SAT.  Proving that 3SAT is _NP-complete_ does.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T22:21:49.193Z
Notice from internal affairs: Even that does not imply difficulty (without further assumptions). [;)]
Raphael
CC BY-SA 2.5
2011-02-08T22:26:13.243Z
@Raphael: I used the word “difficulty” in my previous comment in some intuitive, non-rigorous sense.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-09T08:02:35.060Z
It is counter intuitive that 2D matching is in $P$ but 3D matching is $NP$-complete.
Mohammad Al-Turkistany
<soft-question><intuition>
How do you get a "Physical Intuition" for results in TCS?
gabgoh
# How do you get a "Physical Intuition" for results in TCS?

(Asked by: username_0 on 2011-02-08)

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?

**Tags:** soft-question, intuition
> **Comments:**
> **username_1**: Please do spell-check next time you post.  
> **username_0**: sorry :( will do  
> **username_1**: A message from the NP-completeness police: proving that 3SAT is in NP does not imply the difficulty of 3SAT.  Proving that 3SAT is _NP-complete_ does.  
> **username_2**: Notice from internal affairs: Even that does not imply difficulty (without further assumptions). [;)]  
> **username_1**: @Raphael: I used the word “difficulty” in my previous comment in some intuitive, non-rigorous sense.  
> **username_3**: It is counter intuitive that 2D matching is in $P$ but 3D matching is $NP$-complete.  

---

## 6 answers

### Answer by username_4 on 2011-02-09. Score: 48

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.

> **Comments:**
> **username_5**: Wonderful answer.  
> **username_6**: Let me add one suggestion to Ryan's great answer.  If at some point you get stuck reading someone else's proof, PUT IT DOWN and try to prove the result yourself.  Your belief that the result is probably true (otherwise why would you be reading the paper?) makes it much easier to come up with your own proof.  If you fail, the effort will build up your intuition.  If you succeed, your proof may be VERY different than the proof in the paper you're reading, in which case you have  intuition that the author does not!  I can credit at least three or my papers directly to this trick.  

---

### Answer by username_7 on 2011-02-08. Score: 17

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 by username_1 on 2011-02-08. Score: 16

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’](http://byorgey.wordpress.com/2009/01/12/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. :(

> **Comments:**
> **username_8**: There are undergrads who find undecidability surprising? Do they not teach them about Gödel first?  
> **username_9**: I certainly didn't get Gödel in my undergrad CS education. In fact, I didn't get Gödel as an undergrad at all. (This was at an EECS dept., mind you, but nonetheless)...  
> **username_7**: Given what I know about monads, they might as well be burritos ;)  
> **username_3**: Oh man I miss Floridian burritos, Do they send them delivery overseas? :)  
> **username_10**: @Suresh: I suspect the most useful analogy for you might be "Moore closures are to posets as monads are to categories". You can get awfully far in category theory by treating categories as lattices with multiple ways for one element to be below another.  

---

### Answer by username_11 on 2011-02-08. Score: 12

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 by username_12 on 2011-02-09. Score: 12

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 by username_13 on 2012-03-31. Score: 1

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.


---

