Optimizer (E.g. algorithm designer): This theorem is good because you can devise an algorithm using it.

Mathematician: This theorem is good because it has a nice proof, or it is surprising, or it generalizes many known ideas.

Just another WordPress.com weblog

Optimizer (E.g. algorithm designer): This theorem is good because you can devise an algorithm using it.

Mathematician: This theorem is good because it has a nice proof, or it is surprising, or it generalizes many known ideas.

Advertisements

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.

This work was done almost two years ago, when I was an undergrad in Sharif. After being rejected two times, the Ars Combinatoria journal accepted to publish it after revisions. The referee have made quite a few comments/suggestions. I was modifying it during the last 12 days. Today the final (revised) version was created, approved by all authors and sent to the corresponding author. If accepted, this would be my first publication. Well done and congratulations!