Student Thesis STUD-2573

BibliographyLaun, Jürn-Jochen: Natürliche Beweise.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Student Thesis No. 2573 (2007).
37 pages, german.
CR-SchemaF.1.0 (Computation by Abstract Devices General)
F.1.3 (Complexity Measures and Classes)
KeywordsNatürliche Beweise; Untere Schranken; P/Poly; Pseudozufall
Abstract

Das zentrale Problem der Komplexitätstheorie ist die Suche nach unteren Schranken, also Ergebnissen der Form "Die Sprache B ist nicht in der Klasse C". Fast immer werden solche Beweise nach folgendem Schema durchgeführt: Zunächst wird eine Eigenschaft angegeben, die keine Sprache in C hat. Dann wird gezeigt, dass B diese Eigenschaft besitzt. Razborov und Rudich beobachteten, dass alle bisher verwendeten Eigenschaften zwei Gemeinsamkeiten aufweisen: Sie werden nicht nur von B, sondern von einer großen Menge von Sprachen erfüllt und sie lassen sich leicht berechnen. Solche Beweise heißen "natürlich". Razborov und Rudich zeigten, dass natürliche Beweise auf viele Fragen, darunter das P vs. NP-Problem keine Antwort geben können.

Diese Arbeit gibt einen Überblick über das Themengebiet der natürlichen Beweise. Zunächst wird der zentrale Satz von Razborov und Rudich ausführlich dargestellt und eine in ihrer Originalarbeit nur behauptete stärkere Form bewiesen. Dann wird die Untersuchung von Beweistechniken auf Natürlichkeit anhand zweier Beispiele vorgeführt. Schließlich werden Rudichs Erweiterung auf NP-natürliche Beweise und die Anwendung auf maßtheoretische Fragestellungen durch Regan, Sivakumar und Cai vorgestellt.

Full text and
other links
PostScript (947634 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
ContactKontakt per eMail: launjn@studi.informatik.uni-stuttgart.de
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateApril 18, 2007
   Publ. Computer Science