Komplexitätstheorie

In diesem Kurs behandeln wir die Grundlagen der Komplexitätstheorie. Im Besonderen helfen Ihnen die Inhalte dieses Kurses folgenden Situation:

 

Angenommen Ihre Chefin oder Ihr Betreuer hat Sie damit beauftragt ein Programm zu schreiben. Sie haben ein halbes Jahr daran gearbeitet und denken, dass es nicht möglich ist und kein anderer Mensch in der Welt es lösen kann. Wie überzeugen Sie Ihre Chefin? Welche wissenschaftlichen Argumente gibt es in so einer Situation?

 

Um zu beweisen, dass ein algorithmisches Problem gut lösbar ist, gibt man einen Algorithmus an. Aber wie zeigt man, dass ein algorithmisches Problem schwer lösbar oder gar unlösbar ist?