In den Jahren 1998 bis 2002 durfte ich zusammen mit Professor Ernst Specker (1920 – 2011) das Seminar über Algorithmik und Logik an der ETH veranstalten. Die Zusammenarbeit mit Ernst war überaus freundlich, und das Logikseminar hat mir sehr viel Spaß gemacht. Im Sommersemester 2002 führten wir das Logikseminar zuletzt durch, damit endete auch die lange Tradition dieses Seminars, das 1939 erstmalig von Paul Bernays (1888 – 1977) veranstaltet worden ist. Zum Abschluss gab es am 2. Juli 2002 einen Vortrag Glanz und Elend der Logik.
Weitere Informationen liefern die Artikel von George Szpiro vom 1.7.2002 in der NZZ und vom 28.7.2002 in der NZZ am Sonntag.
Paul Bernays ist seit dem Jahre 1934, als er seine Lehrtätigkeit an der Eidg. Technischen Hochschule aufnahm, der Vertreter der mathematischen Logik und Grundlagenforschung in der Schweiz gewesen. Seit 1953 war Ernst Specker Mitveranstalter dieses Seminars.
Informationen zu Paul Bernays liefert der folgende Artikel.
Ernst Specker:
Paul Bernays
LOGIC COLLOQUIUM 78, 381-389
Themen der Jahre 1998 bis 2002
Vier Logiken, Sommersemester 2002
Es sind die folgenden Themen vorgesehen:
- Mehrwertige Logik: Nicht nur Wahrscheinlichkeitswerte wahr/falsch.
- Intuitionistische Logik: Logik der Mathematik, in der die Objekte als mentale Konstrukte aufgefasst werden.
- Quantenlogik: Berücksichtigt, dass zwei Grössen nicht immer simultan messbar sind.
- Modale Logik: Aussagen A werden durch Operatoren moduliert, wie: A ist beweisbar
Die drei ersten Logiken sind Alternativen zur klassischen Logik; sie sollen unabhängig davon entwickelt werden. Modaloperatoren erweitern jede Logik.Literatur:
- Alternatives to Classical Logic, Handbook of Philosophical Logic, Vol. III, Reidel Publishing Company, 1986
Quantenalgorithmen, Wintersemester 2001/2002
Die Beobachtung, dass sich gewisse Quanteneffekte klassisch nicht in Echtzeit simulieren lassen, hat zur Suche nach „Quantencomputern“ geführt, d. h. Computern, die umgekehrt Berechnungen auf Grund von Quanteneffekten wesentlich schneller durchführen als konventielle Computer (wie etwa Turing Maschinen). Ein wichtiger Schritt ist das Resultat von Peter Shor aus dem Jahre 1994. Er beschreibt einen Algorithmus, der auf einem solchen „idealen Quantencomputer“ Zahlen in polynomialer Zeit in Primzahlen zerlegt.
Literatur:
- E.G. Rieffel, W. Polak: An Introduction to Quantum Computing for Non-Physicists
Kombinatorische Spiele, Sommersemester 2001
Kombinatorische Spiele sind Zweipersonenspiele, deren Ausgang (Gewinn/Verlust/Unentschieden) weder von der Geschicklichkeit (wie beim Tennis) noch vom Zufall (wie bei Würfelspielen) noch von Hellsehkunst (wie bei Kartenspielen) abhängt.Der Prototyp eines kombinatorischen Spieles ist das Nim-Spiel: Gegeben sind einige Haufen von Spielmarken. Die beiden Spieler verringern abwechselnd einen der Haufen (was „ganz wegnehmen“ einschliesst). Gewonnen hat, wer zuletzt ziehen kann.
Frage: Welche ersten Züge führen bei 4 Haufen mit 2, 3, 5, 7 Marken zum Gewinn?
Die Theorie der kombinatorischen Spiele beschränkt sich nicht einfach darauf, für einzelne Spiele Ratschläge zu erteilen. Es werden vielmehr Äquivalenzklassen von Spielen eingeführt und auf diesen Klassen Operationen definiert. So kann dann etwa das obige Nimspiel (2, 3, 5, 7) aufgefasst werden als Summe der 4 Spiele (2), (3), (5), (7).
Literatur:
-
- J.H. Conway: On Numbers and Games, Academic Press, 1976
- J.H. Convay: Über Zahlen und Spiele, Vieweg, 1983
- R.K. Guy: Combinatorial Games, Chapter 43 in Handbook of Combinatorics, Elsevier Science, 1995
Descriptive Complexity, Wintersemester 2000/2001
Die Darstellungskomplexität untersucht die Beziehung zwischen den beiden folgenden Fragen
- In welchen formalen Sprachen kann ein Problem formuliert werden?
- Wie aufwendig ist die Lösung des Problems?
Beispiele von Sprachen, Problemen, Aufwand: Prädikatenlogik erster Stufe, „Ist ein vorgelegter Graph zusammenhängend?“, Platzbedarf zur Lösung des Problems.Literatur:
- Neil Immerman: Descriptive Complexity, Graduate Texts in Computer Science, Springer-Verlag Telos; ISBN: 0387986006
Quantenlogik, Sommersemester 2000
Die klassische Aussagenlogik setzt voraus, dass zwei Aussagen durch und/oder verknüpfbar sind. Dass dies nicht selbstverständlich ist, zeigt die Quantentheorie.
Entsprechend der klassischen Logik als einer Theorie der Boole’schen Verbände wird im ersten Teil des Seminars die Q-Logik als Theorie partieller Boole’scher Verbände entwickelt. Die Frage, ob sich in einem System verborgene Parameter einführen lassen, kann dann interpretiert werden als Frage, ob eine partielle Boole’sche Algebra zu einer totalen erweitert werden kann.
Literatur:
- Jeffrey Bub: Interpreting the quantum world, Cambridge University Press, 1997
Modallogik, Wintersemester 1999/2000
Modaloperatoren ordnen einem Satz Φ einen anderen zu, etwa
1. Φ ist beweisbar.
2. Ich weiss, dass Φ.
3. A weiss, dass B nicht weiss, ob Φ.
4. Φ ist notwendig.
Im Seminar sollen Kapitel 1 (Klassische Aussagenlogik als Grundlage) und 3 (Einführung in die Modallogik) des nachfolgend genannten Buches behandelt werden. Zusätzlich werden Anwendungen der Modallogik auf die Operatoren »beweisbar« und »weiss, dass« betrachtet.
Literatur:
- Alexander Chagrov, Michael Zakharyaschev: Modal Logic, Clarendon Press, 1997
Algebraische Komplexitätstheorie, Sommersemester 1999
Ausgehend von einfachen Problemen (z.B. Länge von Additionsketten) sollen einige Kapitel aus dem genannten Buch behandelt werden:
- Straight-Line Programs
- Computation Sequences
- Universality of the Determinant
- Completeness of the Permanent
- Branching and Connectivity
Literatur:
- Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi: Algebraic Complexity Theory, Springer Verlag, 1997
Approximative Beweise, Wintersemester 1998/99
Ziel des Seminars ist der Beweis des PCP-Theorems (Probabilistically Checkable Proofs). PCP0:=PCP(log(n),1) ist eine Klasse von Problemen, definiert auf Grund des Begriffs „stochastisch verifizierbar“. Das Theorem besagt PCP0=NP (Klasse der in polynomieller Zeit verifizierbaren Probleme).
Aus der Definition von PCP folgt unmittelbar, dass NP eine Teilmenge von PCP0 ist. Die Umkehrung wird geführt mit Hilfe von Klassen PCPk (k=1,2), für welche entsprechende Inklusionen gezeigt werden. Diese Klassen sind auch für sich allein betrachtet bedeutsam, besonders auch auf Grund ihrer Anwendung in der Approximationstheorie.
Literatur:
- Mayr, Prömel, Steger (Eds.): Lectures on Proof Verification and Approximation Algorithms, LNCS 1367, Springer, 1998
Komplexitätstheorie, Sommersemester 1998
Ziel des Seminars ist es, einige Aspekte der Komplexitätstheorie zu erarbeiten; an dieser Schnittstelle zwischen Logik und Informatik sollen neben den klassischen Resultaten auch neuere Beweismethoden vorgestellt werden.
Die Komplexitätstheorie untersucht Fragen der folgenden Art: Sei K eine Klasse von Strukturen (z.B. Graphen) und E eine Eigenschaft (z.B. dreifärbbar). Welchen Aufwand erfordern Algorithmen für die Entscheidung / Beweis (deterministische / nichtdeterministische Berechnung), dass eine Struktur aus K der Grösse n die Eigenschaft E besitzt. Masse für den Aufwand sind: Schrittzahl (Zeitkomplexität) und Speicherbedarf (Raumkomplexität). Zusammen mit der Alternative deterministisch / nicht-deterministisch ergibt dies die „klassischen“ Klassen TIME, NTIME, SPACE, NSPACE.
Hierzu sind auf Grund neuerer Beweismethoden weitere Klassen getreten: IP („interactive proofs“) und PCP („probabilistically checkable proofs“).
Literatur
- D.P. Bovet, P. Crescenzi: Introduction to the Theory of Complexity, Prentice Hall, 1994
- S. Hougardy, H.J. Prömel, A. Steger: Probabilistically checkable proofs and their consequences for approximation algorithms, Discrete Mathematics 136 (1994), 175-223
Konrad Schlude