Week 1 (15. & 18. Sept. 2026)

Lecturers: Hans-Joachim Böckenhauer (organisation), Dennis Komm (content)
Course text: J. Hromkovič, Theoretische Informatik, 5. Auflage (Springer Vieweg). The lecture follows it almost 1:1. The English edition has reduced scope.
Covered: Lecture 1 (15.09., slides 1–38), Lecture 2 (18.09., slides 1–29 plus handwritten part: start of Hromkovič Ch. 2, “Alphabete, Wörter, Sprachen”)

Course organisation (Lecture 1, Böckenhauer)

• Lectures: Tue + Fri, 08:00–10:00, HG E 7. In the first week there was also a stream to HG E 5, which will stop.
• Moodle holds everything: forum (use it instead of e-mail, so everyone gets the same information), exercise sheets, solutions, quizzes, enrolment in exercise groups.
• Exercise groups: Tue/Wed/Thu afternoons, about 17–18 groups, including one English group per day. Enrolment opened 15.09. at 12:00, for about one week. The first sessions were in week 2.
• Written homework: a weekly sheet (1–2 tasks), uploaded Friday after the lecture, due one week later via Moodle. You may submit in teams of up to 3, and should then join the same exercise group. Sheets are corrected and graded, and model solutions follow a week later.
• Moodle quiz: weekly, done individually, auto-graded. Open from Friday noon until roughly Monday evening or Tuesday noon, before the next exercise session. The content is exam-relevant and the points count toward admission.
• Worked examples: about every 2nd–3rd week. A video explains something not covered in the lecture, and you solve a similar task in the exercise group. These are not graded and not needed for midterm admission, but the content is exam material.
• Two voluntary midterms (Zwischenprüfungen): around 5–10 Nov and early/mid Dec, probably Mon or Fri 16–18. Exact dates were not yet fixed.
  • Admission requires 50 % of the homework + quiz points accumulated up to each midterm.
  • The average grade of both midterms can be adopted as the final grade, by signing a form at the end of the semester. In that case you skip the session exam.
  • Stay registered for the session exam in myStudies anyway. Otherwise the grade cannot be entered.
  • Historical pass rate is about 80 %.
• The session exam is in Jan/Feb.
• All materials are also in English.

---

1. Executive Overview & Core Objectives

The course asks two questions:

1. Computability (Berechenbarkeit): what can a computer provably never do, in any model, language or future technology?
2. Complexity (Komplexität): of what can be computed, how efficiently (time, space)?

Week 1 is a fast “trailer” (explicitly not the normal pace). Cantor’s diagonalisation, Turing’s undecidability argument, P vs. NP and polynomial-time reductions are previewed and will be done formally later. The handwritten part of Lecture 2 then starts the formal foundations: alphabets, words and the operations on words (Hromkovič §2.2).

Learning objectives. After this week you should be able to:

• define gleich groß, abzählbar, überabzählbar, and give explicit bijections $\mathbb{N}\to {\mathbb{N}}_{+}$ and $\mathbb{N}\to \mathbb{Z}$;
• reproduce Cantor’s diagonal proof that $[0,1{]}_{\mathbb{R}}$ is uncountable, including the $0.0\overline{9}=0.1$ subtlety;
• explain why a precise mathematical definition of “problem” and “algorithm” is needed;
• define a decision problem (Entscheidungsproblem) as a language and model PRIM, TSP/HC, CLIQUE and IND-SET this way;
• state the Church–Turing thesis and its contrapositive;
• reproduce the diagonal argument showing DIAG is undecidable;
• explain why the halting problem is hard intuitively (the Goldbach program);
• define $\mathcal{O}$-notation, P, polynomial-time verifier, NP and NP-completeness;
• explain why $P\subseteq NP$, and why “NP = not polynomial” is wrong;
• carry out and prove correct the reduction CLIQUE → IND-SET;
• use the Ch. 2 vocabulary precisely: $\Sigma$, ${\Sigma }^{\ast }$, ${\Sigma }^{+}$, $\lambda$, $|w|$, $|w{|}_a$, Nummer, Bin, concatenation, reversal, iteration, Teilwort/Präfix/Suffix, canonical order.

---

2. Core Concepts & Formal Definitions

2.1 Historical frame: from Leibniz to Turing

Who	What	Point for us
Leibniz (1646–1716)	“Calculemus!” (Lassen Sie uns rechnen): every question could eventually be settled by calculation	The dream that everything is computable
Russell (1872–1970)	Russell’s paradox (Russellsche Antinomie)	Naive set theory is contradictory
Hilbert (1862–1943)	Hilbert’s program: a system of axioms in which every true statement is provable and no contradiction arises	Wants consistency and completeness
Russell & Whitehead	Principia Mathematica (1910–13): an attempt at a contradiction-free foundation	—
Gödel (1906–1978)	Incompleteness theorem (Unvollständigkeitssatz, 1931): if a (sufficiently strong) system is consistent, there are true statements it cannot prove	Mathematics is and remains incomplete
Turing (1912–1954)	1936: formal definition of algorithm (Turing machine) plus problems no algorithm solves	Birth of CS as a science
Church (1903–1995)	Church–Turing thesis	TM = “algorithm”

Exam Trap: errors in the sources

• Slide 12 gives Gödel’s dates as “1862–1943”. Those are Hilbert’s dates. Gödel lived 1906–1978.
• The lecturer says Church was Turing’s doctoral student. It is the other way round: Turing did his PhD under Church (Princeton, 1938).
• The order “Hilbert, then Russell–Whitehead” is loose. Principia (1910–13) predates Hilbert’s program in its formalised form (1920s). The exam will not test this, but don’t reproduce the wrong order.

2.2 Sizes of infinite sets

Definition (gleich groß / equal size)

Two sets $A$ and $B$ are equally large (gleich groß), written $|A|=|B|$, if there is a bijection (Bijektion) $f:A\to B$. That is, the elements can be paired one-to-one with nothing left over on either side.

This also applies to infinite sets, and that is where intuition fails. Removing an element, or “doubling” a set, need not change its size.

Definition (abzählbar / countable)

An infinite set $A$ is countable (abzählbar) if $|A|=|\mathbb{N}|$, i.e. there is a bijection $\mathbb{N}\to A$. Equivalently, every element of $A$ gets a unique natural-number “index”, so $A$ can be listed as $a_0,a_1,a_2,\dots$
An infinite set that is not countable is uncountable (überabzählbar).

Convention: $\mathbb{N}=\{0,1,2,\dots \}$ (includes 0), ${\mathbb{N}}_{+}=\mathbb{N}\setminus \{0\}$, ${\mathbb{N}}_{\text{gerade}}=\{0,2,4,\dots \}$, ${\mathbb{N}}_{\text{ungerade}}=\{1,3,5,\dots \}$.

Facts stated in Lecture 1 (slides 17–21)

1. $|{\mathbb{N}}_{\text{gerade}}|=|{\mathbb{N}}_{\text{ungerade}}|$
2. $|{\mathbb{N}}_{+}|=|\mathbb{N}|$, although intuitively ${\mathbb{N}}_{+}$ “should” be smaller
3. $\mathbb{Z}$ is countable, although intuitively $|\mathbb{Z}|=2\cdot |\mathbb{N}|$
4. ${\mathbb{Q}}^{+}$ and $\mathbb{Q}$ are countable, although this looks like “infinity × infinity”
5. Satz: $\mathbb{R}$ is not countable (überabzählbar). It even suffices to look at $[0,1{]}_{\mathbb{R}}$.

Exam Trap: "abzählbar" for finite sets

The slide defines abzählbar only for infinite sets. Many textbooks call a set countable if it is finite or in bijection with $\mathbb{N}$. Check which convention the book uses before relying on it in a proof.

2.3 What is a problem? (informal preview, Lecture 1)

Definition (Alphabet, Wort — preview version)

An alphabet (Alphabet) is a finite, non-empty set of symbols. A word (Wort) is a finite string of symbols from the alphabet.
Example: ${\Sigma }_{\text{dez}}=\{0,1,\dots ,9\}$ (the digits, not the decimal numbers). $x=13817$ is a word over ${\Sigma }_{\text{dez}}$. It can be interpreted as the number 13 817, but first and foremost it is just a string.

Definition (Entscheidungsproblem / decision problem)

Given a set $L$ of words, the decision problem for $L$ is: for a given word $x$, decide whether $x\in L$. The answer is always JA or NEIN.
Sets of words are called languages (Sprachen). Interesting languages are usually infinite, although each of their words is finite.

The modelling looks trivial (yes/no) but is very general. The whole of computability and complexity theory can be built on it. Results transfer to search problems (Suchprobleme), e.g. actually outputting a clique instead of just saying “yes”.

Examples:

• $PRIM=\{y\mid y\text{ is (the decimal representation of) a prime}\}$. Asking “is $x$ prime?” is the same as asking “is $x\in PRIM$?”. $PRIM=\{2,3,5,7,11,13,\dots \}$.
• $TSP=\{y\mid y\text{ encodes a graph with a Hamiltonian cycle}\}$. Graphs are encoded e.g. as adjacency matrices (Adjazenzmatrix): a 0/1 string, plus delimiters if needed. A Hamiltonian cycle (Hamiltonkreis) is a cycle that visits every vertex exactly once and returns to the start. A graph with a vertex of degree 1 can never have one.

Exam Trap: "TSP" on the slides is really the Hamiltonian-cycle problem

The slides call the language of graphs with a Hamiltonian cycle “TSP”. Strictly, that is the Hamiltonian cycle problem (HC). The real Traveling Salesperson Problem works on weighted complete graphs and asks for a tour of minimum (or at most $k$) cost. In a formal exam answer, use the definition the task gives you.

2.4 What is an algorithm?

The Wikipedia-style definition (“an unambiguous procedure for solving a problem or class of problems, consisting of finitely many well-defined single steps”) is not a mathematical object:

• What counts as a “single step” (Einzelschritt)? Multiplication? Bitwise addition? A memory jump?
• Under this definition, recipes, directions and user manuals are also “algorithms”.
• Without a formal definition you cannot prove limits. Someone can always say “my notion of algorithm can do more”.

Turing’s idealised human computer (Turing 1936, On Computable Numbers, with an Application to the Entscheidungsproblem; Turing was about 24). A mathematician has:

• a pen that never runs out,
• unboundedly much squared paper,
• a finite set of rules (arithmetic, logic, …), never makes mistakes and never tires.

Procedure:

• Input: a word on the paper.
• Loop: look at the symbol under the pen; depending on it and the internal rules, possibly overwrite it and move the pen one cell left or right; repeat.
• Termination: eventually she is done; she halts (hält).
• Output: the word now on the paper.

Abstraction: 2D paper becomes a one-dimensional tape (Band); the rules become a finite control (endliche Kontrolle) with states (Zustände); the pen position becomes the read/write head (Lese-/Schreibkopf). This is the Turing machine (TM). It will be defined formally later.

Church–Turing-These (Church–Turing thesis)

Turing machines can compute exactly what algorithms can compute (“effectively computable”, effektiv berechenbar).
Contrapositive (the important direction): what a TM cannot compute, no algorithm can compute: not in Java, C++, Ruby on Rails or Python, not with quantum computers, randomised or genetic algorithms, neural networks or LLMs.

Intuition: why the thesis is a thesis, not a theorem

“Effectively computable” is an informal notion, so it cannot be proved equivalent to a formal one. The evidence: every reasonable model of computation ever proposed (real computers, quantum computers, transformers, …) can be simulated by a TM. Exotic ideas such as “throw a computer into a black hole to get infinite time” are not reasonable models.

2.5 Undecidability

Satz von Turing (Turing's theorem)

There are decision problems that cannot be solved by any TM, and hence (by Church–Turing) by no algorithm. Such problems are called undecidable (unentscheidbar).

Core idea: there are only countably many TMs/algorithms, but uncountably many problems. The concrete witness is the language $DIAG$ (proof in §3.5).

Definition (DIAG, informal version from the lecture)

Enumerate all TMs $M_1,M_2,M_3,\dots$ and all words over a fixed alphabet $w_1,w_2,w_3,\dots$
$DIAG=\{w_i\mid M_i\text{ answers NEIN on }{w}_i\}$

Halting problem (Halteproblem), preview: given source code (in any language), decide whether it terminates. This is closely related to DIAG and is proved undecidable later.

2.6 Running time and efficiency

Running time is measured as a function of the input length $n$ (Eingabelänge), not as absolute seconds. “Is 5 prime?” is easy, but “is 10 000 000 013 prime?” should take longer for any method, since you at least have to read the input.

Exam Trap: input length, not input value

For PRIM, the input $x$ is given in binary (or decimal) with $n$ digits. Without leading zeros, $2^{n-1}\le x\le 2^n-1$, so $x\approx 2^n$. An algorithm that is linear in the value $x$ is therefore exponential in the length $n$.
(The transcript says “from $2^n-1$ to $2^n-1$”; the correct range is $[2^{n-1},2^n-1]$.)

Definition ( $\mathcal{O}$-Notation)

For functions $f,g:\mathbb{N}\to {\mathbb{R}}_{\ge 0}$:
$f\in \mathcal{O}(g)⟺\exists c>0\exists n_0\in \mathbb{N}\forall n\ge n_0:f(n)\le c\cdot g(n)$
Informally: for large $n$, $f$ grows at most a constant factor faster than $g$. $\mathcal{O}(g)$ is a set of functions.

Slide examples: $4n^2\in \mathcal{O}(n^2)$, $100n^3\in \mathcal{O}(n^3)$, $100n^3+50n\in \mathcal{O}(n^3)$, $5n\in \mathcal{O}(n^2)$, $n^3\notin \mathcal{O}(n^2)$, $2^n\notin \mathcal{O}(n^2)$.

Growth table (slide 18.09., p. 5):

$n$	10	50	100	300	10 000
$4n^2$	400	10 000	40 000	360 000	400 000 000
$n^3$	1 000	125 000	1 000 000	27 000 000	13 digits
$2^n$	1 024	16 digits	31 digits	91 digits	3 011 digits
$3^n$	59 049	24 digits	48 digits	143 digits	4 772 digits

These von Cobham und Edmonds (Cobham–Edmonds thesis)

Efficient algorithms are those that run in polynomial time: running time in $\mathcal{O}(n^k)$ for some constant $k\in \mathbb{N}$.
$\mathcal{O}(n^3)$ and $\mathcal{O}(n^{10})$ are efficient; $\mathcal{O}(1.41^n)$ is not.
(The transcript spells the names “Coppern” and “Koppel”; the correct name is Alan Cobham.)

Why “some polynomial” and not a fixed degree?

1. Robustness: if a “real” algorithm (x86, smartphone, …) solves a problem in $\mathcal{O}(n^k)$, a TM solves it in $\mathcal{O}(n^{k^{\prime }})$ for some possibly larger constant $k^{\prime }$, and vice versa. Polynomial time does not depend on the model; a fixed exponent would.
2. Empirical: once some polynomial algorithm is found for a natural problem, the exponent usually gets pushed down to something reasonable (e.g. primality testing).
3. Even $n^{100000000}$ is eventually far smaller than $2^n$.

Definition (Klasse P)

P is the class of all decision problems that can be solved by a TM in polynomial time (“efficiently”).
We say class rather than set to avoid the “sets of sets” issues from Russell.

Examples in P: minimum spanning tree (Kruskal, Prim from A&D) and PRIM (“PRIMES is in P”, Agrawal–Kayal–Saxena 2002, which grew out of undergraduate work).

Exam Trap: PRIM is in P, but the naive tests are not polynomial

Both trial-division tests from the slides (§4.2) are exponential in $n$. PRIM $\in$ P needs the much cleverer AKS algorithm. The lecturer recalled the original exponent as about $n^7$, later reduced towards $n^{4+\epsilon }$. In the literature as I know it, the original proven bound is $\tilde{\mathcal{O}}(n^{12})$, improved to $\tilde{\mathcal{O}}(n^6)$ (Lenstra–Pomerance). Either way: polynomial.

Running time always means worst case. For even inputs both naive prime tests stop immediately; the worst case is a prime input.

2.7 Polynomial-time verifiers and NP

Definition (Polynomzeit-Verifizierer, PV — informal)

A polynomial-time verifier does not have to compute the answer itself. Along with the input $x$ it receives a string $z$, a (potential) witness (Zeuge/Zeugin):

• if $x$ is a JA-instance, there exists a witness that proves it, and the PV then answers JA;
• if $x$ is a NEIN-instance, the witness can be arbitrary nonsense, and the PV must answer NEIN for every witness.

The PV must run in polynomial time in $|x|$. Implicitly, this means the witness must also have polynomial length.

Example (Hamiltonian cycle): a TM gets the graph and must decide whether a Hamiltonian cycle exists; no efficient method is known. A PV gets the graph plus a witness such as $v_1,v_3,v_5,v_4,v_6,v_2,v_1$ and only checks it: every vertex appears exactly once, the cycle closes, and every consecutive pair is an edge. This is efficient.

Definition (Klasse NP)

NP is the class of all decision problems that can be solved efficiently by a PV.
“N” stands for nichtdeterministisch (nondeterministic). PVs are an equivalent reformulation of polynomial-time nondeterministic TMs, which come later.

Exam Trap: NP does NOT mean "not polynomial"

NP = Nondeterministic Polynomial time. NP is not “the hard problems”. Every problem in P is also in NP. NP is the superclass of P within which we still have hope of finding polynomial algorithms. The lecturer said he would be “personally hurt” if you leave the course thinking NP = “nicht polynomiell”.

Satz: $P\subseteq NP$ (proof in §3.6)

Consequences:

• If a problem is outside NP (not even efficiently verifiable), it is certainly not efficiently solvable.
• P vs. NP: is $P=NP$ or $P⊊NP$? Open. Most researchers believe $P⊊NP$. It is one of the Millennium Prize Problems (USD 1 000 000). It could even be unprovable (compare Gödel).
• Sad fact: for no problem in NP can we prove a superlinear lower bound for general TMs. Only $\Omega (n)$ is known (you have to read the input).

2.8 NP-completeness and reductions

Definition (NP-vollständig — informal version from the lecture)

A problem $A\in NP$ is NP-complete (NP-vollständig) if the efficient solvability of $A$ implies the efficient solvability of all problems in NP.
So if an efficient TM is ever found for one NP-complete problem, then $P=NP$. If one is ever proved to have no polynomial algorithm, then $P\ne NP$.

Satz von Cook (Cook's theorem, 1971)

There exists an NP-complete decision problem: SAT (Boolean satisfiability).

Karp (1972)

There are 21 further NP-complete problems. Today thousands are known (TSP/HC, CLIQUE, IND-SET, graph colouring, …), and for none can we prove that no efficient TM exists.

Exam Trap: dates

The transcript says a mathematician “came in 1972” and showed the existence of an NP-complete problem, and later “Cook in ‘72”. Cook’s theorem is 1971 (Levin independently); Karp’s 21 problems are 1972.

Definition (Clique, Independent Set)

Let $G=(V,E)$ be an undirected, unweighted graph.

• $S\subseteq V$ is a clique (Clique) if all vertices of $S$ are pairwise connected: $\forall u\ne v\in S:\{u,v\}\in E$.
• $S\subseteq V$ is an independent set (unabhängige Menge) if no two vertices of $S$ are connected: $\forall u\ne v\in S:\{u,v\}\notin E$.
  $CLIQUE=\{(G,k)\mid G\text{ has a clique of size }k\}$
  $IND\text{-}SET=\{(G,k)\mid G\text{ has an independent set of size }k\}$
  $k\in \mathbb{N}$ is part of the input, not a fixed constant.

Definition (Polynomzeit-Reduktion — informal)

We reduce problem $A$ to problem $B$ by showing: if $B$ could be solved efficiently, then $A$ could be solved efficiently too. Concretely, build an efficient algorithm for $A$ that uses a hypothetical efficient algorithm for $B$ as a black box. Intuitively, $B$ is then at least as hard as $A$.

Recipe for proving $B$ NP-complete:

1. Show $B\in NP$.
2. Pick an $A$ already known to be NP-complete.
3. Reduce $A$ to $B$.
4. Conclude by transitivity: efficient $B$ ⇒ efficient $A$ ⇒ efficient everything in NP.

Believed picture (slide 18.09., p. 26): P and the NP-complete problems are disjoint subclasses inside NP. If $P=NP$, they all collapse.

2.9 Formal foundations: alphabets and words (Hromkovič §2.2, handwritten part of Lecture 2)

Definition (Alphabet)

An alphabet (Alphabet) is any finite, non-empty set. Its elements are called letters/symbols (Buchstaben, Symbole). Usually denoted $\Sigma$, which is not a sum sign.
Examples:

• ${\Sigma }_{\text{bool}}=\{0,1\}$ (Boolean alphabet). For computability you can almost always restrict to it.
• ${\Sigma }_{\text{lat}}=\{a,b,c,\dots ,z\}$ (lower-case Latin letters)
• ${\Sigma }_{\text{Tastatur}}$ (keyboard symbols); Unicode or ASCII, or subsets of them
• ${\Sigma }_{\text{logic}}=\{0,1,x,(,),\wedge ,\vee ,\neg \}$ ($x$ as a placeholder for variables)

Definition (Wort, Länge, leeres Wort, ${\Sigma }^{\ast }$, ${\Sigma }^{+}$)

Let $\Sigma$ be an alphabet.

• A word over $\Sigma$ (Wort über $\Sigma$) is a finite sequence of symbols from $\Sigma$. It is written without commas or brackets, e.g. $01101$ over ${\Sigma }_{\text{bool}}$, although formally it is a tuple.
• The length (Länge) $|w|$ of a word $w$ is the number of positions in $w$, e.g. $|0110|=4$.
• The empty word (leeres Wort) $\lambda$ is the unique word of length 0. Other books write $\epsilon$; this course uses $\lambda$.
• ${\Sigma }^{\ast }$ is the set of all words over $\Sigma$ (Kleene star, as in regular expressions).
• ${\Sigma }^{+}={\Sigma }^{\ast }-\{\lambda \}$ is the set of all non-empty words. The book writes set difference with a minus sign.

${\Sigma }_{\text{bool}}^{\ast }=\{\lambda ,0,1,00,01,10,11,000,\dots \}{\Sigma }_{\text{bool}}^{+}=\{0,1,00,01,10,11,000,\dots \}$

Exam Trap: length counts positions, not distinct symbols

$|01101|=5$, although only 2 distinct symbols occur.
Also: $\lambda$ is a word, $\{\lambda \}$ is a language with one element, and $\varnothing$ is the language with no elements. So $\{\lambda \}\ne \varnothing$.
In Lecture 2 the lecturer said ”${\Sigma }_{\text{bool}}^{\ast }$ would be the same without $\lambda$”. He misspoke: the set without $\lambda$ is ${\Sigma }_{\text{bool}}^{+}$.

Definition (Nummer and Bin: numbers as words)

For $x=x_1{x}_2\cdots x_n\in {\Sigma }_{\text{bool}}^{\ast }$ (each $x_i\in {\Sigma }_{\text{bool}}$), $x$ is interpreted as a binary number:
$\text{Nummer}(x)={\sum }_{i=1}^n{x}_i\cdot 2^{n-i}$
The least significant bit is on the right: $x_1$ gets weight $2^{n-1}$, $x_n$ gets $2^0=1$. For $x=\lambda$ the empty sum gives 0; this case is not of practical interest here.
Conversely, for $m\in \mathbb{N}-\{0\}$, $\text{Bin}(m)$ is the binary representation of $m$ without leading zeros (the shortest one). Additionally $\text{Bin}(0)=0$.

Intuition: Nummer and Bin are not inverse bijections

$\text{Nummer}(\text{Bin}(m))=m$ always holds. But $\text{Nummer}$ is not injective: $\text{Nummer}(0101)=\text{Nummer}(101)=5$. $\text{Bin}$ picks the canonical representative.
Words are just strings. The problem determines their interpretation: a number, an adjacency matrix, a formula, …

Definition (Verkettung / Konkatenation)

For an alphabet $\Sigma$, the concatenation is the map
$\text{Kon}:{\Sigma }^{\ast }\times {\Sigma }^{\ast }\to {\Sigma }^{\ast },\text{Kon}(x,y)=x\cdot y=xy$
i.e. $y$ is written directly after $x$. The dot is usually omitted.
Example: $x=01$, $y=11$, so $xy=0111$.
$\lambda$ is neutral: $x\lambda =\lambda x=x$ and $\lambda \lambda =\lambda$. Concatenation is associative but not commutative ($01\cdot 1=011\ne 101=1\cdot 01$). Hence $({\Sigma }^{\ast },\cdot )$ is a monoid; this remark is from the book, not stated in the lecture. $|xy|=|x|+|y|$.

Definition (Umkehrung / reversal)

For $w=a_1{a}_2\cdots a_n$ with $a_i\in \Sigma$, the reversal (Umkehrung) of $w$ is
$w^R=a_n{a}_{n-1}\cdots a_1$
Example: $(001{)}^R=100$. Also ${\lambda }^R=\lambda$.

Definition (Iteration)

For $x\in {\Sigma }^{\ast }$ and $i\in \mathbb{N}$, the $i$-th iteration $x^i$ of $x$ is defined recursively:
$x^0=\lambda ,x^1=x,x^i=x^{i-1}\cdot x(i\ge 2)$
The book writes $x^i=x{x}^{i-1}$; both are equal by associativity.
Example $x=ab$: $x^0=\lambda$, $x^1=ab$, $x^2=abab$, $x^3=ababab$, …
Iteration is also used on single letters inside words: $abbbbab=a{b}^{4}ab$. Careful: the exponent applies only to the symbol directly before it (see §4.5).

Definition (Teilwort, Präfix, Suffix)

Let $v,w\in {\Sigma }^{\ast }$.

• $v$ is a subword (Teilwort, also Infix) of $w$ if $\exists x,y\in {\Sigma }^{\ast }$: $w=xvy$.
• $v$ is a prefix (Präfix) of $w$ if $\exists y\in {\Sigma }^{\ast }$: $w=vy$.
• $v$ is a suffix (Suffix) of $w$ if $\exists x\in {\Sigma }^{\ast }$: $w=xv$.

Lecture convention: $v$ is a proper (echtes) subword if additionally $x\ne \lambda$ and $y\ne \lambda$.
Naming convention (not always kept): letters $a,b,c,\dots$; words $u,v,w,x,y$. The lecturer names the trailing piece $y$ (as in the book), even though a student suggested $x$.

Exam Trap: "proper" has several conventions

The lecture’s version of echt ($x,y\ne \lambda$) is stricter than the common convention "$v\ne w$" (often also "$v\ne \lambda$"). Under the lecture’s version, a prefix $v\ne w$ is not automatically a proper subword, because there $x=\lambda$. In exams, use the definition the task gives; if none is given, use the book’s.
Also: $\lambda$ is a prefix, suffix and subword of every word, and $w$ is a prefix, suffix and subword of itself.

Definition ( $|x{|}_a$)

For $x\in {\Sigma }^{\ast }$ and $a\in \Sigma$, $|x{|}_a$ denotes the number of occurrences (Anzahl der Vorkommen) of the letter $a$ in $x$.
Example: $|01101{|}_1=3$, $|01101{|}_0=2$, and ${\sum }_{a\in \Sigma }|x{|}_a=|x|$.

Definition (kanonische Ordnung / canonical order)

Let $\Sigma =\{s_1,s_2,\dots ,s_m\}$ be an alphabet with an order $s_1<s_2<\cdots <s_m$ on its letters. The canonical order on ${\Sigma }^{\ast }$ is: for $u,v\in {\Sigma }^{\ast }$,
$u<v⟺|u|<|v|\text{or}(|u|=|v|\text{and}u=x{s}_i{u}^{\prime },v=x{s}_j{v}^{\prime }\text{with }x,u^{\prime },v^{\prime }\in {\Sigma }^{\ast },i<j)$
In words: first by length, then lexicographically at the first differing position. The common prefix $x$ may be $\lambda$.
Example: $0010<0100$ (common prefix $0$, then $0<1$). Over ${\Sigma }_{\text{bool}}$: $\lambda <0<1<00<01<10<11<000<\dots$

Exam Trap: canonical order ≠ dictionary order

Pure lexicographic (dictionary) order on $\{a,b{\}}^{\ast }$ would put $a<aa<aaa<\cdots <b$. Infinitely many words come before $b$, so it does not enumerate ${\Sigma }^{\ast }$ as a list $w_1,w_2,\dots$. Sorting by length first fixes this: there are only finitely many ($m^{\ell }$) words of each length $\ell$. This is exactly why the canonical order is used to enumerate words in diagonal arguments.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Russell’s paradox (Lecture 1, slides 8–9)

Define $S=\{X\mid X\text{ is a set and }X\notin X\}$, the set of all sets that do not contain themselves. Example from the lecture: $A=\{1,2,3\}$ does not contain itself, so $A\in S$. A set $B$ that (hypothetically) contains itself would not be in $S$.

Question: is $S\in S$? There are only two possibilities.

1. Assume $S\in S$. Then $S$ is a set containing itself. But $S$ contains exactly the sets that do not contain themselves. So $S\notin S$. Contradiction.
2. Assume $S\notin S$. Then $S$ is a set that does not contain itself, so by definition of $S$, $S\in S$. Contradiction.

Both cases are contradictory, so naive set formation (“every property defines a set”) is inconsistent. This is the same structure as Pinocchio saying “My nose will grow now” (it grows iff he lies): if the statement is true, he lied, so it is false; if it is false, he lied, so the nose grows and it is true.

Intuition: the common pattern behind Russell, Gödel, Cantor and Turing

Each argument builds an object that talks about itself in a negated way (“the set of sets that do not contain themselves”, “the word $w_i$ is in DIAG iff $M_i$ does not accept $w_i$”, “the number differing from the $i$-th number in the $i$-th digit”). This self-reference with negation is diagonalisation.

3.2 Explicit bijections (slides 17–19)

${\mathbb{N}}_{\text{gerade}}\to {\mathbb{N}}_{\text{ungerade}}$: $f(2k)=2k+1$. It is injective, and every odd $2k+1$ has the preimage $2k$. ($0$ is even.)

$\mathbb{N}\to {\mathbb{N}}_{+}$: $f(n)=n+1$. Inverse $f^{-1}(m)=m-1$ for $m\ge 1$. Removing one element from an infinite set does not change its size.

$\mathbb{Z}\to \mathbb{N}$ (as described in the lecture): map 0 to 0, positive $z$ to “double minus 1”, negative $z$ to “double with the other sign”:
$g(z)=\{\begin{array}{ll}0& z=0\\ 2z-1& z>0\\ -2z& z<0\end{array}$
Check against slide 19 (read as $\mathbb{N}\to \mathbb{Z}$: $0\mapsto 0,1\mapsto 1,2\mapsto -1,3\mapsto 2,4\mapsto -2$): $g(1)=1$, $g(-1)=2$, $g(2)=3$, $g(-2)=4$. ✓

Why bijective: positive integers go bijectively onto the odd naturals ($z\mapsto 2z-1$), negative integers go bijectively onto the even naturals $\ge 2$ ($z\mapsto -2z$), and $0\mapsto 0$. These three images partition $\mathbb{N}$.

${\mathbb{Q}}^{+}$ is countable (stated, not proved, in the lecture; standard proof added here). Write all fractions $\frac{p}{q}$, $p,q\in {\mathbb{N}}_{+}$, in an infinite grid (row $p$, column $q$). Walk the anti-diagonals $p+q=2,3,4,\dots$, each of which is finite, and skip fractions not in lowest terms ($\frac{2}{2}=\frac{1}{1}$, …). Every positive rational appears exactly once, at a finite position, which gives a bijection with $\mathbb{N}$. This is Cantor’s first diagonal method. For $\mathbb{Q}$, interleave $0$, positives and negatives exactly as for $\mathbb{Z}$.

3.3 $[0,1{]}_{\mathbb{R}}$ is uncountable: Cantor’s diagonal argument (slides 21–23)

Satz

$\mathbb{R}$ is uncountable. It suffices to show that $[0,1{]}_{\mathbb{R}}$ is uncountable.

Proof by contradiction (Widerspruchsbeweis): assume the opposite, derive something absurd (“pigs can fly”), conclude the assumption was false.

1. Assumption: $[0,1{]}_{\mathbb{R}}$ is countable, so there is a list $r_1,r_2,r_3,\dots$ containing every real number in $[0,1]$. The slides number from 0 and use “digit $i$ of row $i$” with an index shift; the idea is identical.
2. Write each $r_i$ in decimal: $r_i=0.d_{i,1}{d}_{i,2}{d}_{i,3}\dots$ Irrational numbers have infinite expansions. That is no problem: the table was already infinite downwards, and now it is infinite to the right as well.
3. Construct $x=0.c_1{c}_2{c}_3\dots$ from the diagonal:
   $c_i=\{\begin{array}{ll}5& \text{if }{d}_{i,i}\ne 5\\ 4& \text{if }{d}_{i,i}=5\end{array}$
   so $c_i\ne d_{i,i}$ for all $i$. Then $x\in [0,1]$, and $x$ is uniquely determined by the table even though we cannot write it down completely.
4. $x$ is not in the list: suppose $x=r_k$ for some $k$. In position $k$, $c_k\ne d_{k,k}$, so $x$ and $r_k$ differ in the $k$-th digit.
5. Why differing in a digit really means a different number (the periodicity issue the lecturer postponed): decimal expansions are not unique, e.g. $0.0999\dots =0.1000\dots$ A differing digit alone could therefore be fooled. Our $x$ uses only digits 4 and 5, never 0 or 9, so $x$ has a unique expansion. If $r_k=x$, every expansion of $r_k$ would equal $x$‘s unique expansion, which differs from row $k$ at digit $k$. Contradiction.
6. Since $k$ was arbitrary, $x$ is in no row. So the list is incomplete, contradicting step 1. ∎

Slide example: the diagonal digits are $2,8,7,4,\dots$ and the slide chooses $x=0.1763\dots$ ($1\ne 2$, $7\ne 8$, $6\ne 7$, $3\ne 4$). Any choice works, as long as it avoids the 0/9 problem.

The method is called diagonalisation (Diagonalisierung), more precisely Cantor’s second diagonal method. (The slide’s “Widerspruch Diagonalisierung” is a typesetting artefact.)

3.4 Countably many algorithms, uncountably many problems (lecture’s high-level claim, made precise)

This was claimed in the lecture; the precise version follows later in the course.

• TMs are countable: every TM has a finite description over a fixed finite alphabet. Mapping each TM to its description is injective into ${\Sigma }^{\ast }$. ${\Sigma }^{\ast }$ is countable: list it in canonical order, which works because there are finitely many words of each length. So TMs can be listed $M_1,M_2,\dots$ (the “Gödelisierung”/encoding of TMs comes later).
• Languages are uncountable: a problem is a language $L\subseteq {\Sigma }^{\ast }$. Suppose all languages were listed $L_1,L_2,\dots$ and the words $w_1,w_2,\dots$ in canonical order. Define $L=\{w_i\mid w_i\notin L_i\}$. Then $L\ne L_i$ for every $i$, because they disagree on $w_i$. This is §3.3 with “digit” replaced by “membership”.
• Conclusion: there are more languages than TMs, so some language has no TM.

3.5 DIAG is undecidable (slides 34–37)

Setup: list all TMs $M_1,M_2,\dots$ and all words $w_1,w_2,\dots$ (e.g. binary words in canonical order: $\lambda ,0,1,00,01,10,11,000,\dots$). Build an infinite table whose cell $(i,j)$ is J if $M_i$ answers JA on $w_j$ and N otherwise.

Example: if $M_{129}$ happened to be the PRIM machine, its row would read N on 0, N on 1, J on 2, J on 3, N on 4, J on 5, …

Definition: $w_i\in DIAG⟺$ the diagonal entry $(i,i)$ is N, i.e. $M_i$ does not answer JA on $w_i$. Slide example: diagonal J, N, N, J, … gives $DIAG=\{w_2,w_3,\dots \}$.

Claim: no TM decides DIAG.

Proof by contradiction:

1. Assume a TM $M$ decides DIAG: it answers JA exactly on the words of DIAG.
2. $M$ is a TM, so it appears in the list: $M=M_k$ for some $k$ (e.g. the 325 000th).
3. Look at cell $(k,k)$:
   • Case J: $M_k$ answers JA on $w_k$. By definition of DIAG, $w_k\notin DIAG$. But $M_k$ decides DIAG, so it must answer NEIN on $w_k$. Contradiction.
   • Case N: $M_k$ answers NEIN on $w_k$. By definition, $w_k\in DIAG$. But then $M_k$, being correct for DIAG, must answer JA. Contradiction.
4. Both cases are impossible, so no such $M$ exists. DIAG is undecidable. ∎

Exam Trap: TMs need not halt

The lecture’s table assumes each TM answers J or N on every word. Real TMs may run forever. The formal version (later) reads “N” as “does not accept” (rejects or never halts): $DIAG=\{w_i\mid M_i\text{ does not accept }{w}_i\}$. The argument still works. If you write “rejects” instead of “does not accept” in a formal proof, it becomes subtly wrong.

Intuition: why care about such an artificial language?

DIAG is constructed specifically to be undecidable, so it seems esoteric. But it is the starting point: via reductions, undecidability of DIAG transfers to natural problems such as the halting problem, which we would very much like to solve (compilers, verification).

3.6 $P\subseteq NP$

Let $L\in P$, decided by a TM $M$ in time $\mathcal{O}(n^k)$. Build a PV $V$: on input $(x,z)$, ignore $z$ and run $M$ on $x$.

• If $x\in L$, any witness (e.g. $z=\lambda$) leads to JA.
• If $x\notin L$, $V$ answers NEIN for every $z$.

$V$ runs in polynomial time, so $L\in NP$. ∎ (A PV gets the same problem plus extra information, so it can only be at least as capable.)

3.7 Why a reduction transfers NP-completeness (slide 21)

Let $A,B\in NP$ with $A$ NP-complete.

1. $A$ NP-complete means: an efficient algorithm for $A$ gives an efficient algorithm for every $L\in NP$.
2. The reduction shows: an efficient algorithm for $B$ gives an efficient algorithm for $A$.
3. By chaining: an efficient algorithm for $B$ gives an efficient algorithm for $A$, hence for every $L\in NP$. Together with $B\in NP$, $B$ is NP-complete. ∎

The direction matters: reduce the known-hard problem to the new one (“my problem is at least as hard as yours, because solving mine solves yours for free”).

3.8 Reduction CLIQUE → IND-SET with correctness proof

Complement graph: for $G=(V,E)$ let $\overline{G}=(V,\overline{E})$ with $\overline{E}=\{\{u,v\}\mid u,v\in V,u\ne v,\{u,v\}\notin E\}$. Delete existing edges and insert edges exactly where there were none. Same vertex set, no self-loops.

Lemma

$S\subseteq V$ is a clique in $G$ $⟺$ $S$ is an independent set in $\overline{G}$.
$S\text{ clique in }G⟺\forall u\ne v\in S:\{u,v\}\in E⟺\forall u\ne v\in S:\{u,v\}\notin \overline{E}⟺S\text{ independent in }\overline{G}$
The middle equivalence holds because for $u\ne v$, exactly one of $\{u,v\}\in E$ and $\{u,v\}\in \overline{E}$ is true.

Reduction algorithm (slide 25): given a hypothetical efficient TM $B$ for IND-SET, the following decides CLIQUE:

1. Input $(G,k)$.
2. Compute $\overline{G}$: flip every off-diagonal entry of the adjacency matrix.
3. Run $B$ on $(\overline{G},k)$ with the same $k$, and output its answer.

Correctness: $(G,k)\in CLIQUE⟺G$ has a $k$-clique $⟺$ (Lemma) $\overline{G}$ has an independent set of size $k⟺(\overline{G},k)\in IND\text{-}SET⟺B$ answers JA.

Efficiency: with $|V|=m$, step 2 touches $m^2$ entries, so it is linear in the input length $N\approx m^2$. The output has the same size $N$. If $B$ runs in $p(N)$, the whole algorithm runs in $\mathcal{O}(N)+p(\mathcal{O}(N))$, which is polynomial.

Membership: IND-SET $\in NP$. The witness is a set $S$ of $k$ vertices; check $|S|=k$ and the $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ pairs against the matrix in polynomial time. So: if CLIQUE is NP-complete, IND-SET is NP-complete.

Converse: the same construction reduces IND-SET to CLIQUE (since $\overline{\overline{G}}=G$). Both problems are equally hard in this sense.

Exam Trap: the reduction must be efficient AND produce small output

A reduction is only useful if (a) the transformation itself runs in polynomial time and (b) its output has polynomial size. Otherwise plugging it into a polynomial black box need not give polynomial total time.

3.9 Running time of the naive prime tests (slides 18.09., p. 6)

Input $x$ with $n$ bits, so $2^{n-1}\le x<2^n$.

• Test 1 (try every divisor $2\le t<x$): for a prime $x$ (the worst case) the loop runs $x-2\approx 2^n$ times, so the time is $\Theta (2^n)$.
• Test 2 (try divisors up to $\sqrt{x}$): this is enough by the following lemma.

Lemma

If $x\ge 2$ is composite, $x$ has a nontrivial divisor $a$ with $2\le a\le \sqrt{x}$.
Proof. $x=ab$ with $2\le a\le b$. If $a>\sqrt{x}$ then $b\ge a>\sqrt{x}$, so $ab>x$. Contradiction. ∎

Iterations $\approx \sqrt{x}\approx \sqrt{2^n}=(\sqrt{2}{)}^n\approx 1.414^n$. This is much better than $2^n$, but still exponential. The plots on slides 8–9 show $2^n$ and $1.415^n$ both shooting “vertically” upward, while $n^2$ and $n^3$ stay flat. The first plot’s axis range was deliberately chosen so that $1.415^n$ looks harmless.

Exam Trap: an exponential with a "small base" is still exponential

$1.41^n\notin \mathcal{O}(n^k)$ for every $k$. Exponentials with base $>1$ dominate every polynomial.

---

4. Worked Examples & Applications

4.1 The Goldbach program: why the halting problem is not “just read the code” (slide 38)

Three programs: print("Hello, world."); exit() clearly halts. while True: i = 1 (followed by unreachable prints) clearly never halts, ignoring hardware failure and memory limits. Now the interesting one, from the slide:

n = 4                      # Initialisierung
p = 1
while True:
    p = p + 1
    if isprime(p):
        q = n - p
        if isprime(q):     # p und q sind prim und n = p + q
            print(n + "=" + p + "+" + q)
            n = n + 2
            p = 1
    if p > n/2:            # Keine Primzahlen p und q mit n = p + q gefunden
        exit()

Trace:

• $n=4$: $p=2$ is prime, $q=2$ is prime. Print “4=2+2”, then $n=6$, $p=1$.
• $n=6$: $p=2$, $q=4$ (not prime). $p=3$, $q=3$ (prime). Print “6=3+3”, then $n=8$.
• $n=8$: $p=2$, $q=6$ no; $p=3$, $q=5$ yes. Print, then $n=10$. And so on.

What it does: for $n=4,6,8,\dots$ it searches for primes $p\le n/2$ with $n-p$ also prime. It halts iff it finds an even $n\ge 4$ that is not a sum of two primes.

Goldbach conjecture (Goldbach-Vermutung): every even integer $\ge 4$ is the sum of two primes. It is open, though checked by computer to very large bounds. The program halts $⟺$ Goldbach is false.

So even with perfect understanding of these 12 lines, we cannot say whether the program terminates without settling an open conjecture. This is not a proof of undecidability, only a teaser that “inspect the code carefully (with Copilot)” cannot work in general.

Exam Trap: details in the slide code

• The transcript says “even numbers greater than 4”. Goldbach is about even numbers $\ge 4$ (equivalently $>2$).
• As literal Python, n + "=" + p raises a TypeError (int + str). It is pseudocode in Python syntax. Correct would be print(f"{n}={p}+{q}").

4.2 The two prime tests (slides 18.09., p. 6)

# Test 1: alle Teiler 2..zahl-1
test = 2
while test < zahl:
    rest = zahl % test
    if rest == 0:
        print("Nein"); exit(0)
    test = test + 1
print("Ja"); exit(0)

# Test 2: nur bis zur Wurzel
test = 2
wurzel_zahl = sqrt(zahl)
while test <= wurzel_zahl:
    rest = zahl % test
    if rest == 0:
        print("Nein"); exit(0)
    test = test + 1
print("Ja"); exit(0)

Example: zahl = 97 (prime, $n=7$ bits since $64\le 97<128$)

• Test 1: tests $2,\dots ,96$, i.e. 95 iterations, no divisor found, so “Ja”. Compare $2^7=128$.
• Test 2: $\sqrt{97}\approx 9.85$, tests $2,\dots ,9$, i.e. 8 iterations, so “Ja”. Compare $1.414^7\approx 11.3$.
• For zahl = 98 (even) both stop after 1 iteration. Worst case is a prime.

4.3 Verifier for the Hamiltonian-cycle problem (slide 18.09., p. 15)

Input: a graph on $v_1,\dots ,v_6$. Witness: $v_1,v_3,v_5,v_4,v_6,v_2,v_1$.

Verification steps, each polynomial:

1. First vertex = last vertex? $v_1=v_1$ ✓
2. Do the inner vertices $v_1,v_3,v_5,v_4,v_6,v_2$ contain each of the 6 vertices exactly once? ✓
3. Is each consecutive pair an edge, i.e. adjacency entry 1 for $\{v_1,v_3\}$, $\{v_3,v_5\}$, $\{v_5,v_4\}$, $\{v_4,v_6\}$, $\{v_6,v_2\}$, $\{v_2,v_1\}$? If all ✓, answer JA.

If the graph had no Hamiltonian cycle, any witness must fail one check. For example, if $\{v_6,v_2\}\notin E$, check 3 fails and the PV answers NEIN. This is correct, because for a JA-instance a correct witness would have been supplied.

Cost: $\mathcal{O}(m)$ checks for $m$ vertices, each an $\mathcal{O}(1)$ matrix lookup (on a TM: polynomial).

4.4 The live Python demo of the reduction (Lecture 2, after the break)

The lecturer coded the reduction live to show that the “black box” picture is just ordinary program composition. Cleaned-up version:

def solve_independent_set(G, k):
    """Black box: assumed to decide IND-SET in polynomial time (we don't know how)."""
    ...
 
def solve_clique(G, k):
    n = len(G)                          # G: adjacency matrix (list of lists of 0/1)
    H = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:                  # keep the diagonal at 0: no self-loops
                H[i][j] = 1 - G[i][j]   # complement every off-diagonal entry
    return solve_independent_set(H, k)  # same k

Exam Trap: the diagonal of the adjacency matrix

In the live demo the lecturer flipped every entry, including the diagonal, and said “on the diagonal there should actually only be ones”. That is a slip. For simple graphs the diagonal is 0 (no loops), and the complement must keep it 0, hence the i != j above. The lecturer acknowledged he was being sloppy.

Example: does $G$ = single edge between two vertices have a clique of size 2?

$G=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$, $k=2$. The complement is $H=\left[\begin{array}{cc}0& 0\\ 0& 0\end{array}\right]$ (no edges). $\{v_1,v_2\}$ is an independent set of size 2 in $H$, so the black box returns True. Indeed $\{v_1,v_2\}$ is a 2-clique (an edge) in $G$. The demo printed True.

4.5 Word operations (handwritten part, Lecture 2)

Example: in-lecture questions

• $\text{Kon}(01,11)=0111$.
• Q: what is $x\cdot \lambda$ for $x=011$? A: $x$. Likewise $\lambda x=x$, $\lambda \lambda =\lambda$, $\lambda \lambda \lambda =\lambda$.
• Q: what is $x^0$? A (student): $\lambda$.
• Q: natural recursive definition of $x^i$? A (student): $x^i=x^{i-1}x$.
• $(ab{)}^4=abababab$; $abbbbab=a{b}^{4}ab$.
• $(001{)}^R=100$.
• $|0110|=4$; $\text{Nummer}(1101)=8+4+0+1=13$; $\text{Bin}(13)=1101$; $\text{Bin}(0)=0$.
• Canonical order: $0010<0100$.

Exam Trap: precedence of iteration

$a{b}^4$ means $abbbb$, not $(ab{)}^4$. The exponent binds only to the immediately preceding symbol unless brackets are used.

4.6 Student questions

Student question (Lecture 2): are there decidable problems that provably cannot be solved in polynomial time?

Yes. There is a large hierarchy of complexity classes above P (the time hierarchy theorem gives decidable problems requiring exponential time). This comes later. What is open is whether such a problem lies inside NP: no problem in NP is known to be outside P.

Clarification (Lecture 2): "But sorting has an $n\log n$ lower bound!"

The $\Omega (n\log n)$ bound from A&D holds for comparison-based sorting, a restricted model (Radix sort and Bucket sort are not comparison-based). For general TMs we cannot prove any bound above $\Omega (n)$ for NP problems, i.e. not even $\Omega (n^2)$, although we believe many need about $2^n$.

Question during the break: how do reductions work for harder problem pairs?

CLIQUE ↔ IND-SET is the simplest case (just complement). For other pairs the reductions can be very intricate. They are done in detail later in the course.

---

5. Intuition & Conceptual Bridges

Intuition: why counting proves impossibility

Each algorithm is a finite text, so there are countably many. Each problem is an arbitrary subset of ${\Sigma }^{\ast }$, so there are uncountably many. Most problems therefore have no algorithm. Diagonalisation makes this concrete by constructing one such problem (DIAG). It is the same move as constructing a real number missing from any list.

Intuition: the existence vs. non-existence asymmetry

To show a problem is in P, you show one algorithm and verify it (e.g. Kruskal for MST). To show it is not in P, you would have to rule out all algorithms ever. “I found none, nor did anyone else” is weak evidence, but it is roughly the best we have. NP-completeness turns this weakness into a strong structural statement: “if you crack this one, you crack thousands at once, and many brilliant people have failed”.

Intuition: why the strange verifier model?

No real computer gets the answer whispered to it. The PV model is a thought tool: it defines the largest natural class (NP) where we cannot yet rule out efficient algorithms. Checking a solution seems easier than finding it, and P vs. NP asks whether that intuition is provably true.

Intuition: MST vs. Hamiltonian cycle

A spanning tree through all vertices (easy, in P) and a cycle through all vertices (HC, NP-complete) look almost the same. Yet one is efficiently solvable and the other believed not to be. Small changes in a problem can cause huge jumps in complexity.

Connections to prior courses:

• Diskrete Mathematik: bijections, countability, Cantor, proof by contradiction, possibly Gödel numbering.
• Algorithmen und Datenstrukturen: $\mathcal{O}$-notation, worst-case analysis, MST (Kruskal/Prim), the comparison-based sorting lower bound.

Where the course goes next (slide 18.09., p. 28):

1. Finite automata (endliche Automaten) and regular languages (reguläre Sprachen), closely related to regular expressions (that is where the Kleene star ${\Sigma }^{\ast }$ comes from). They are strongly restricted TMs, so concepts such as nondeterminism are easy to study there first.
2. Gradually more general models, up to formal Turing machines.
3. Computability: encoding TMs as words (Gödelisierung), formal DIAG, the halting problem, reductions for undecidability.
4. Complexity: formal P, NP (nondeterministic TMs and verifiers), polynomial-time reductions, Cook’s theorem (SAT), NP-completeness proofs.

The Ch. 2 vocabulary ($\Sigma$, ${\Sigma }^{\ast }$, $\lambda$, $|w|$, concatenation, iteration, canonical order, Nummer/Bin) is used constantly from now on. Canonical order is exactly what enumerates $w_1,w_2,\dots$ in DIAG.

---

6. Summary & Self-Assessment Questions

Cheat table

Concept	Key statement
gleich groß	$|A|=|B|$ iff there is a bijection $A\to B$
abzählbar	(infinite) $A$ with $|A|=|\mathbb{N}|$; ${\mathbb{N}}_{+},\mathbb{Z},\mathbb{Q}$ are countable
überabzählbar	$\mathbb{R}$, $[0,1{]}_{\mathbb{R}}$, the set of all languages $\mathcal{P}({\Sigma }^{\ast })$
Diagonalisation	build an object that differs from the $i$-th listed object at position $i$
Church–Turing thesis	TM = algorithm; not TM-computable means not computable at all
DIAG	$w_i\in DIAG$ iff $M_i$ does not accept $w_i$; undecidable
$\mathcal{O}$	$f\in \mathcal{O}(g)$ iff $\exists c,n_0\forall n\ge n_0:f(n)\le cg(n)$
Efficient	polynomial time $\mathcal{O}(n^k)$ (Cobham–Edmonds)
P	decision problems solvable by a TM in polynomial time
NP	decision problems solvable by a polynomial-time verifier (nondeterministic polynomial)
Known relations	$P\subseteq NP$; $P=NP$? open; believed $P⊊NP$
NP-complete	$A\in NP$, and efficient $A$ implies all of NP efficient
Cook 1971 / Karp 1972	SAT is NP-complete / 21 more NP-complete problems
Reduction $A\to B$	efficient $B$ implies efficient $A$; reduce from known-hard $A$ to new $B$
CLIQUE → IND-SET	$(G,k)\mapsto (\overline{G},k)$, cost $\mathcal{O}(|V{|}^2)$
Alphabet	finite, non-empty set $\Sigma$
${\Sigma }^{\ast }$, ${\Sigma }^{+}$	all words; all non-empty words (${\Sigma }^{\ast }-\{\lambda \}$)
$\lambda$	empty word, $|\lambda |=0$, neutral for concatenation
$\text{Nummer}(x)$	${\sum }_{i=1}^n{x}_i{2}^{n-i}$
$\text{Bin}(m)$	binary of $m$ without leading zeros; $\text{Bin}(0)=0$
$x^i$	$x^0=\lambda$, $x^i=x^{i-1}x$
$w^R$	$a_n\cdots a_1$
Teilwort/Präfix/Suffix	$w=xvy$ / $w=vy$ / $w=xv$
$|x{|}_a$	number of occurrences of $a$ in $x$
Canonical order	by length first, then lexicographically at the first differing position

Self-assessment questions

Question 1. Give the bijection $g:\mathbb{Z}\to \mathbb{N}$ from the lecture. Compute $g(-3)$ and $g(4)$, and find $g^{-1}(7)$ and $g^{-1}(10)$. Prove that $g$ is a bijection.

Solution to Question 1

$g(0)=0$, $g(z)=2z-1$ for $z>0$, $g(z)=-2z$ for $z<0$.

• $g(-3)=6$, $g(4)=7$.
• $7$ is odd, so it comes from a positive $z$ with $2z-1=7$, i.e. $z=4$: $g^{-1}(7)=4$.
• $10$ is even and $\ne 0$, so it comes from a negative $z$ with $-2z=10$, i.e. $z=-5$: $g^{-1}(10)=-5$.

Injective: the three cases map into the pairwise disjoint sets $\{0\}$, the odd numbers, and the even numbers $\ge 2$. Within a case the map is affine with nonzero slope, hence injective.
Surjective: $0=g(0)$; odd $m$ gives $m=g\left(\frac{m+1}{2}\right)$ with $\frac{m+1}{2}>0$; even $m\ge 2$ gives $m=g(-\frac{m}{2})$. ∎

Question 2. In Cantor’s proof, why does the lecture (and the book) need to “be careful with periodicity”? Construct a list $r_1,r_2,\dots$ for which the naive rule "$c_i=d_{i,i}+1\mathrm{mod}10$" produces a number $x$ that is in the list.

Solution to Question 2

Some reals have two decimal expansions: $0.1000\dots =0.0999\dots$ The diagonal argument proves only that $x$ differs from row $k$ as a digit string. If the two strings are different expansions of the same real, $x$ could still be in the list.

Counterexample to the naive rule. We want $x=0.1000\dots$ to appear in the list in its other form $0.0999\dots$

• Rule $c_i=d_{i,i}+1\mathrm{mod}10$. To get $c_1=1$ we need $d_{1,1}=0$; to get $c_i=0$ for $i\ge 2$ we need $d_{i,i}=9$.
• Let $r_1=0.0999\dots$ (so $d_{1,1}=0$), and choose $r_2,r_3,\dots$ as any listing of reals whose $i$-th digit $d_{i,i}$ is 9 (such expansions are easy to choose).
• Then $x=0.1000\dots =0.0999\dots =r_1$. So $x$ is in the list, and the argument breaks.

Fix: use only digits that cannot create double expansions, e.g. $c_i=5$ if $d_{i,i}\ne 5$, else $c_i=4$. Then $x$ has a unique expansion and the contradiction is valid.

Question 3. Prove carefully that DIAG is undecidable. State where the proof uses that DIAG talks about the diagonal, and why the answer “N” must be read as “does not accept”.

Solution to Question 3

Enumerate the TMs $M_1,M_2,\dots$ (possible because each has a finite description, so there are countably many). Enumerate the words $w_1,w_2,\dots$ in canonical order.
$DIAG=\{w_i\mid M_i\text{ does not accept }{w}_i\}$.

Suppose a TM $M$ decides DIAG. Then $M=M_k$ for some $k$. Consider $w_k$, the word on the diagonal position $(k,k)$; this is where the definition of DIAG refers to $M_k$ itself.

• If $M_k$ accepts $w_k$, then $w_k\notin DIAG$ by definition. But $M_k$ decides DIAG, so it must not accept $w_k$. Contradiction.
• If $M_k$ does not accept $w_k$, then $w_k\in DIAG$. Since $M_k$ decides DIAG, it accepts $w_k$. Contradiction.

So no TM decides DIAG. ∎

Why “does not accept”: a TM can reject or loop forever. If DIAG were defined as ”$M_i$ rejects $w_i$”, looping machines would fall outside both cases and the case split would not be exhaustive. “Accepts / does not accept” is a true dichotomy.

Question 4. True or false? Justify each.
(a) NP is the class of problems that cannot be solved in polynomial time.
(b) If IND-SET $\in P$, then $P=NP$, assuming CLIQUE is NP-complete.
(c) To show a new problem $B$ is NP-hard, reduce $B$ to a known NP-complete problem $A$.
(d) For TSP/HC we know a lower bound of $\Omega (2^n)$ for general TMs.

Solution to Question 4

(a) False. NP = nondeterministic polynomial time. $P\subseteq NP$, so NP contains all efficiently solvable problems. Whether NP contains problems outside P is exactly the open P vs. NP question.

(b) True. CLIQUE reduces to IND-SET via $(G,k)\mapsto (\overline{G},k)$ in polynomial time. A polynomial algorithm for IND-SET therefore gives one for CLIQUE. Since CLIQUE is NP-complete, this gives one for every problem in NP, so $NP\subseteq P$, and with $P\subseteq NP$ we get $P=NP$.

(c) False (wrong direction). Reducing $B$ to $A$ only shows “efficient $A$ implies efficient $B$”, i.e. $B$ is no harder than $A$. You must reduce the known-hard $A$ to $B$.

(d) False. For general TMs, no lower bound above the trivial $\Omega (n)$ (read the input) is known for any problem in NP. Lower bounds like $\Omega (n\log n)$ for sorting hold only in restricted models (comparison-based).

Question 5. Let $\Sigma =\{a,b\}$ with $a<b$, $x=ab$, $y=ba$.
(a) Compute $(xy{)}^R$, $x^3$, $|x^{3}y{|}_a$, $|x^{3}y|$.
(b) List all prefixes and all suffixes of $w=abba$. Is $bb$ a subword? Is it proper in the lecture’s sense?
(c) Sort canonically: $ba,aab,\lambda ,b,ab,aa$.
(d) Compute $\text{Nummer}(00101)$, $\text{Bin}(18)$, and explain why $\text{Bin}(\text{Nummer}(00101))\ne 00101$.

Solution to Question 5

(a)

• $xy=abba$, so $(xy{)}^R=abba$ (a palindrome).
• $x^3=x^{2}x=(abab)ab=ababab$.
• $x^{3}y=abababba$. Count of $a$: positions 1, 3, 5, 8, so $|x^{3}y{|}_a=4$. Length $|x^{3}y|=8$ (check: $3\cdot 2+2$).

(b) Prefixes of $abba$: $\lambda ,a,ab,abb,abba$. Suffixes: $\lambda ,a,ba,bba,abba$.
$bb$ is a subword: $w=xbby$ with $x=a$, $y=a$. Since $x\ne \lambda$ and $y\ne \lambda$, it is a proper subword in the lecture’s sense.

(c) By length first: length 0: $\lambda$; length 1: $b$; length 2: $aa,ab,ba$ (lexicographic: $aa<ab$ at position 2, and $ab<ba$ at position 1); length 3: $aab$.
Result: $\lambda <b<aa<ab<ba<aab$.

(d)

• $\text{Nummer}(00101)=0\cdot 2^4+0\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=5$.
• $18=16+2$, so $\text{Bin}(18)=10010$.
• $\text{Bin}(5)=101\ne 00101$, because $\text{Bin}$ removes leading zeros. $\text{Nummer}$ is not injective (all of $101,0101,00101,\dots$ map to 5), so $\text{Bin}$ is only a right inverse: $\text{Nummer}\circ \text{Bin}=\text{id}$, but $\text{Bin}\circ \text{Nummer}\ne \text{id}$.