General information

Subtitle	P vs NP Survival Guide
Course number	INF-0384
Semester	SS 2022
Current number of participants	4
Home institute	Resource Aware Algorithmics
Courses type	Seminar in category Teaching
Online/Digitale Veranstaltung	Veranstaltung wird online/digital abgehalten.
Hauptunterrichtssprache	deutsch

Lecturers

Prof.Dr. Tobias Mömke

Tutor

Course location / Course dates

unspecified

Fields of study

Fakultät für Angewandte Informatik > Informatik

Module assignments

Informatik B.Sc. Informatik, PO 2013, 17. Version > B.Sc. Informatik (PO '13) - Informatik-Vertiefung > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)
Informatik B.Sc. Informatik, PO 2018, 8. Version gültig bis SS 2022 > Seminar > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)
Auslandsstudium FAI Austauschstudium FAI, 1. Version > FakultÃ¤t fÃ¼r Angewandte Informatik - Bachelor Level > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)
Austauschstudium - Phil.-Soz. Austauschstudium, 1. Version gültig bis SS 2022 > FakultÃ¤t fÃ¼r Angewandte Informatik - Bachelor Level > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)
Informatik und Multimedia B.Sc. Informatik und Multimedia, PO 2013, 17. Version > B.Sc. Informatik und Multimedia (PO '13) - Informatik und Multimedia-Vertiefung > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)
Informatik und Multimedia B.Sc. Informatik und Multimedia, PO 2013, 16. Version gültig bis SS 2022 > B.Sc. Informatik und Multimedia (PO '13) - Informatik und Multimedia-Vertiefung > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)
Informatik und Multimedia B.Sc. Informatik und Multimedia, PO 2016, 13. Version > B.Sc. Informatik und Multimedia (PO '15) - Informatik und Multimedia-Vertiefung > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)
Informatik B.Sc. Informatik, PO 2013, 16. Version gültig bis SS 2022 > B.Sc. Informatik (PO '13) - Informatik-Vertiefung > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)
Informatik B.Sc. Informatik, PO 2018, 9. Version > Seminar > INF-0384 - Seminar Resource Aware Algorithmics (Bachelor) > Seminar Resource Aware Algorithmics (Bachelor)

Comment/Description

Das Seminar beschäftigt sich mit dem Thema P vs NP. Die Frage ob P = NP gilt ist äquivalent zur Frage, ob man in einem Straßennetzwerk einen Weg finden kann der alle Städte genau einmal besucht oder zur Frage, ob man in einem Netzwerk von Freunden eine Zahl k von Personen finden kann, die sich alle gegenseitig kennen.

Der fundamentale Charakter dieses bislang ungelösten Problems hat dazu geführt, dass das Clay Mathematics Institute einen Preis von USD 1 000 000 für die Lösung dieses Problems ausgeschrieben hat.

Auf dem Weg dieses Problem zu lösen gibt es jedoch viele Fallen und Sackgassen. Dies führt dazu, dass gelegentlich Nachrichten zur vermeintlichen Lösung dieses Problems in Zeitungen veröffentlicht werden. Bislang war keiner dieser Ansätze korrekt.

In diesem Seminar geht es darum, ein besseres Verständnis zu diesem Problem zu erarbeiten. Eines der Ziele ist es, zumindest einige Fallen als solche zu identifizieren um Fehler zu vermeiden. Es geht um Themen wie zum Beispiel:

- Welche Art von Problemen kann man effizient lösen?
- Gibt es ähnliche Klassen von Problemen bei denen eine Lösung bekannt ist?
- Wie verifiziert man, ob ein P vs NP Beweis korrekt sein kann? Welche Lösungsansätze kann man ausschließen?
- Ist es möglich dass die Frage ob P vs NP unentscheidbar ist?