One reason I like computational complexity is because it’s mysterious: you see surprising results that don’t agree with your common sense. The first example was the equality NL = co-NL, which I saw a few years ago, and has a very elegant proof. And the second example was the PCP e, i.e. NP = PCP (log n, 1), which is quite surprising, and the proof is perhaps very complicated. That’s why you can never be sure that NP\P is nonempty, even if everyone believes it.

For almost the same reason, I liked probability theory when I was in high-school: it is mysterious, and there were lots of paradoxical problems related to probability. Well, when I studied formal probability theory (Kolmogorov axioms etc.) there wasn’t any paradoxes anymore (fortunately?), but I still like it, because of its surprisingly strong applications in graph theory and algorithms.

### Like this:

Like Loading...

*Related*

Tags: computational complexity, probability theory

This entry was posted on February 8, 2010 at 12:13 am and is filed under story. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply