"Berechenbarkeit und Komplexitaet 001.ps.gz" - читать интересную книгу автора

Universit"at Trier Fachbereich IV - Informatik

Christoph Meinel: Berechenbarkeit und

Komplexit"at

Vorlesungsskript SS 1994

INHALTSVERZEICHNIS 1 Inhaltsverzeichnis 1 Berechenbarkeitstheorie 2

1.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These : : : : : 2 1.2 Churchsche These : : : : : : : : : : : : : : : : : : : : : : : : : : 5 1.3 Turing-Berechenbarkeit : : : : : : : : : : : : : : : : : : : : : : : 6 1.4 LOOP-, WHILE- und GOTO-Berechenbarkeit : : : : : : : : : : 14 1.5 Primitiv rekursive und _-rekursive Funktionen : : : : : : : : : : 21 1.6 Die Ackermann-Funktion : : : : : : : : : : : : : : : : : : : : : : 24 1.7 Entscheidbarkeit und Semi-Entscheidbarkeit : : : : : : : : : : : 29 1.8 Das Halte-Problem und die Reduzierbarkeit : : : : : : : : : : : : 33 1.9 Das Postsche Korrespondenz-Problem : : : : : : : : : : : : : : : 38 1.10 Der G"odelsche Unvollst"andigkeitssatz : : : : : : : : : : : : : : : : 44

2 Komplexit"atstheorie 50

2.1 Komplexit"atsmasse und Komplexit"atsklassen : : : : : : : : : : : : 50 2.2 Die Komplexit"atsklassen P und N P : : : : : : : : : : : : : : : : 52 2.3 N P -Vollst"andigkeit : : : : : : : : : : : : : : : : : : : : : : : : : 55 2.4 Weitere N P -vollst"andige Probleme : : : : : : : : : : : : : : : : : 60

2.4.1 3SAT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 2.4.2 CLIQUE : : : : : : : : : : : : : : : : : : : : : : : : : : : 62 2.4.3 HAMILTON-KREIS : : : : : : : : : : : : : : : : : : : : : 63

1 BERECHENBARKEITSTHEORIE 2 1 Berechenbarkeitstheorie 1.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These

ffl Es gibt eine intuitive Vorstellung, welche Funktionen (auf den nat"urlichen

Zahlen) berechenbar sind.

ffl Auf Basis dieser intuitiven Vorstellung k"onnen allerdings keine Beweise

gef"uhrt werden, dass eine bestimmte Funktion nicht berechenbar ist.

ffl Deshalb ist eine formale mathematische Definition der Berechenbarkeit

notwendig.

ffl Der Nachweis der Nichtberechenbarkeit einer Funktion besteht dann darin nachzuweisen, dass die betrachtete Funktion nicht der Definition entspricht.

ffl neues Problem: Begr"undung, dass die formale Definition genau den intuitiven Berechenbarkeitsbegriff erfasst. Dazu ist kein formaler Beweis f"uhrbar, denn der intuitive Berechenbarkeitsbegriff ist nicht formal erfasst.

Beispiele f"ur Funktionen, die intuitiv berechenbar sind: