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.