Computer Science – How Mathematics Courses Enhance Learning in Computability and Complexity Theory

computabilitycomputational complexitycomputer scienceeducation

I'm a senior undergraduate Mathematics student, and I'm about to be a grad Mathematics student in M.Sc. course. Yet I aim to be a Ph.D. in CS.

The reason for this bizarre route is because I'm fascinated by Computability Theory and Complexity Theory. I regard them as branches of pure mathematics, so I decided to have a strong mathematical background.

Yet I don't know how Mathematics courses will help learning Computability Theory and Complexity Theory. Here, I focus on the following courses, which are mandatory:

  • Algebra 1: Groups, rings, fields, vector spaces.

  • Real Analysis 1: Lebesgue measure, Lebesgue integration.

  • Topology 1: Homotopy, fundamental group, Van Kempen's theorem, covering space, group action.

  • Probability Theory 1: Law of large numbers, martingale theory, ergodic theory.

  • Applied Mathematics 1: Functionals, Green's function, Fourier transformation.

  • Complex Analysis: Poisson integral, Schwarz lemma, Phragmén-Lindelöf principle, Runge's theorem, Mittag-Leffler theorem, Riemann mapping theorem.

  • Geometry 1: Curves, surfaces, shape operator, Riemann geometry.

The list of all courses is shown here.

Just in case, I state that I took almost all undergraduate math courses, including all "standard" ones. The followings are the courses I couldn't take:

Algebraic Topology, Topological Data Analysis, Real Analysis (which differs from elementary Analysis), Insurance Mathematics, Financial Mathematics, Industrial Mathematics, Derivative (as in finance) Theory, Practical Data Analysis.

(And sorry if this question is off-topic here. Maybe CS SE or Academia SE is a better place.)

Best Answer

The rise of Computability Theory arguably began (under the name "Recursion Theory") as central concept in the statement and proof of Gödel's Incompleteness Theorems in 1930ies, well before Turing.

In order to prove (essential) undecidability, Logician Tarski employed "computable reductions" in the 1940ies; which Cook in 1971 refined to polynomial-time reduction defining the complexity class NP.

Geometric Complexity Theory is currently counted among the most promising approaches to settle the P/NP Millennium Problem by quantitatively refining known qualitative results in Algebraic Geometry.

Generally speaking, breakthroughs (like Wiles' proof of Fermat's Last Theorem) often arise from exhibiting surprising new connections between/to Mathematical fields.

Related Question