Professional Diploma in Mastering Theoretical Computer Science: Computability and Complexity

The Mastering Theoretical Computer Science: Computability and Complexity course presented by Geneve Institute of Business Management offers a concentrated, concept-driven program that examines the mathematical foundations of what can be computed and how resource demands scale. Across ten instructional units the syllabus guides participants from formal models of computation through decidability limits, complexity classes and reductions, to advanced topics such as completeness, probabilistic computation and space-time trade-offs. Emphasis rests on rigorous definitions, precise reasoning and the ability to translate informal intuitions into formal statements and proofs so learners gain lasting clarity about the boundaries of algorithmic solvability and the intrinsic cost of computation. The programme suits those who seek a solid theoretical toolkit to inform research, advanced development, or technical leadership in areas where correctness and efficiency are essential.

Target group

• Graduate students and advanced undergraduates pursuing rigorous foundations in algorithms, automata and logic.

• Software engineers and researchers who require theoretical grounding to reason about feasibility and algorithmic limits.

• System architects and performance engineers needing formal insight into lower bounds and complexity trade-offs.

• PhD candidates and academics preparing to teach or conduct research in computability, complexity theory or related areas.

• Practitioners in cryptography, verification or compilers who must apply formal models when designing provable systems and protocols.

• Technical leads and product specialists who evaluate algorithmic claims and map theoretical results to system requirements.

Objectives

• Formalise models of computation and apply them to prove whether problems are decidable.

• Classify problems by resource usage, comparing time and space complexity across models.

• Construct reductions to relate problems and demonstrate completeness or hardness within classes.

• Explore nondeterminism, alternation and probabilistic computation and their complexity implications.

• Analyse trade-offs, hierarchies and relativisation phenomena that shape complexity landscapes.

• Translate theoretical results into practical criteria for algorithm selection and system design.

Course Outline

• Mathematical Preliminaries:

  • Sets, relations, functions and basic proof techniques for precise argumentation.

  • Induction, recursion and structural induction over algebraic data types.

  • Asymptotic notation, growth rates and formal comparisons of function classes.

  • Counting arguments, combinatorial estimates and simple enumerative tools.

  Formal Languages and Automata I:

  • Alphabets, strings, languages and operations over languages.

  • Deterministic finite automata (DFA): definitions and closure properties.

  • Nondeterministic finite automata (NFA) and equivalence to DFA.

  • Regular expressions and pumping lemma for regular languages.

• Formal Languages and Automata II:

  • Context-free grammars (CFG) and derivation trees for structured languages.

  • Pushdown automata (PDA) and acceptance modes for CFLs.

  • Normal forms, grammar transformations and pumping lemma for CFLs.

  • Parsing complexity and grammar ambiguity concerns.

  Computability Foundations I:

  • Turing machine model: tape, head movement and formal configuration concept.

  • Variants of Turing machines and robustness of the model.

  • Encodings, decidability definitions and characteristic functions for languages.

  • Church–Turing thesis and implications for informal computability notions.

• Computability Foundations II:

  • Recursive (decidable) versus recursively enumerable (semidecidable) sets and examples.

  • Diagonalisation techniques and simple undecidable languages construction.

  • The Halting Problem: formal statement and proof of undecidability.

  • Reductions for proving undecidability and mapping reducibility concepts.

  Complexity Theory Basics:

  • Time complexity for deterministic Turing machines and formal time bounds.

  • Class P: polynomial-time decision problems and robustness across models.

  • Class NP: nondeterministic polynomial-time definitions and certificate characterisations.

  • Verifiers, NP membership proofs and non-determinism intuition.

• Reductions and NP-Completeness:

  • Polynomial-time many-one reductions and transitivity of hardness relations.

  • Cook–Levin theorem: SAT as NP-complete and its significance.

  • Classic NP-complete problems and common transformation patterns.

  • Techniques for proving NP-hardness and completeness for new problems.

  Space Complexity and Hierarchies:

  • Space-bounded computation: definitions of SPACE(f(n)) and L, NL classes.

  • Savitch’s theorem and relations between nondeterministic and deterministic space.

  • Hierarchy theorems asserting proper containments under resource bounds.

  • Trade-offs between time and space and space-complexity reductions.

• Advanced Complexity Classes:

  • Polynomial hierarchy (PH), Σk and Πk levels and intuition behind alternation.

  • Counting classes (e.g., #P) and relationships to decision problems.

  • Probabilistic classes: BPP, RP, and ZPP definitions and basic properties.

  • Interactive proofs and IP class overview with central results.

  Randomness, Derandomisation and Oracles:

  • Role of randomness in algorithms and one-sided versus two-sided error bounds.

  • Derandomisation concepts and pseudorandom generators at a high level.

  • Oracle machines and relativisation limitations on proof techniques.

  • Natural proofs and barriers to certain complexity separations.

• Completeness, Reductions Beyond NP:

  • Notions of completeness in space-bounded and probabilistic classes.

  • Reductions tailored to counting and optimisation problems.

  • Approximation classes and hardness of approximation framing.

  • Complete problems for higher classes and canonical representatives.

  Cryptographic Complexity Connections:

  • Worst-case to average-case notions and their role in cryptographic assumptions.

  • One-way functions, trapdoor predicates and complexity-theoretic foundations.

  • Reductions used in cryptographic security proofs at a conceptual level.

  • Complexity perspectives on zero-knowledge proofs and secure computation.

• Advanced Proof Techniques:

  • Diagonalisation, padding, and time hierarchy arguments in depth.

  • Circuit complexity basics and the role of uniformity conditions.

  • Lower bound strategies and limitations of current techniques.

  • Communication complexity as a tool to prove lower bounds.

  Descriptive and Parameterised Complexity:

  • Descriptive complexity: logic characterisations of complexity classes.

  • Fixed-parameter tractability (FPT) and kernelisation concepts.

  • W-hierarchy and parametrised hardness notions.

  • Connections between parametrised complexity and practical algorithm design.

• Space-Time Trade-offs and Practical Implications:

  • Formal statements of trade-offs and examples illustrating resource interplay.

  • Time-space lower bounds for specific problems and algorithmic consequences.

  • Implications for parallelism, distributed computation and external-memory algorithms.

  • Using complexity results to inform algorithm selection and system engineering.

  Frontier Topics and Research Directions:

  • Major open problems and their significance: P versus NP, circuit lower bounds.

  • Emerging areas: quantum complexity, fine-grained complexity and average-case analysis.

  • Methodological challenges and promising proof techniques under active study.

  • Pathways to contribute: research practices, literature mapping and community venues.