News

25. November 2021

Das P-NP-Problem: Von leicht und schwer in der Mathematik

Öffentlicher Vortrag von Michael Drmota (TU Wien)

Tafelbild, auf dem das P-NP-Problem dargestellt wird — © privat

Wann & Wo?

Donnerstag, 25. November 2021, 18:00 Uhr
Freihaus TU Wien, Wiedner Hauptstraße 8-10, Hörsaal 8

Abstract

“Das P-NP-Problem ist eines der großen ungelösten Probleme der Mathematik und wurde im Jahr 2000 auch in die Lieste der sieben Millenniumsprobleme aufgenommen. Es geht – kurz gesagt – um die Frage, ob man zwischen leichten (P-) und schweren (NP-) Problemen streng unterscheiden kann: Ist P ungleich NP?
Dabei heißt ein Problem leicht, wenn die Lösung rasch – genauer: in polynomieller Zeit – ermittelt werden kann und schwer, wenn dies nicht erwartet werden kann und es nur leicht ist, eine vorgegebene Lösung auf Korrektheit zu überprüfen.

In diesem Vortrag werden einige P- und NP-Probleme vorgestellt sowie die Geschichte rund um das P-NP-Problem beleuchtet.

Aufzeichnung des Vortrags

Unsere Website verwendet Cookies und bindet Inhalte von Drittanbietern ein, um die grundlegende Funktionalität unserer Website zu gewährleisten sowie die Zugriffe auf unserer Website zu analysieren und um Funktionen für soziale Medien und zielgerichtete Werbung anbieten zu können. Hierzu ist es nötig Informationen an die jeweiligen Dienstanbieter weiterzugeben. Weitere Informationen zu Cookies und Inhalten von Drittanbietern auf der Website finden Sie in unserer Datenschutzerklärung.

Erforderlich

Diese Cookies werden für eine reibungslose Funktion unserer Website benötigt.

Name	Zweck	Ablauf	Typ	Anbieter
CookieConsent	Speichert Ihre Einstellungen zur Verwendung von Cookies auf dieser Website.	1 Jahr	HTML	Homepage TU Wien
SimpleSAML	Wird benötigt, um die Sessions der eingeloggten Benutzer_innen voneinander unterscheiden zu können.	Session	HTTP	Login TU Wien
SimpleSAMLAuthToken	Wird benötigt, um die Sessions der eingeloggten Benutzer_innen voneinander unterscheiden zu können.	Session	HTTP	Login TU Wien
fe_typo_user	Wird benötigt, damit im Falle eines Typo3-Frontend-Logins die Session-ID wiedererkannt wird um Zugang zu geschützten Bereichen zu gewähren.	Session	HTTP	Homepage TU Wien
staticfilecache	Wird benötigt, um die Auslieferungszeit der Website zu optimieren.	Session	HTTP	Homepage TU Wien
JESSIONSID	Wird benötigt, damit im Falle eines LectureTube-Logins die Session-ID wiedererkannt wird um Zugang zu geschützten Bereichen zu gewähren.	Session	HTTP	LectureTube TU Wien
_shibsession_lecturetube	Wird benötigt, um die Sessions der eingeloggten Benutzer_innen voneinander unterscheiden zu können.	Session	HTTP	LectureTube TU Wien

Webstatistiken

Mit Hilfe dieser Cookies können wir unser Angebot laufend verbessern und unsere Website an Ihre Bedürfnisse anpassen. Dabei werden pseudonymisierte Daten über die Websitenutzung gesammelt und statistisch ausgewertet.

Name	Zweck	Ablauf	Typ	Anbieter
_pk_id	Wird verwendet, um ein paar Details über den Benutzer wie die eindeutige Besucher-ID zu speichern.	13 Monate	HTML	Matomo TU Wien
_pk_ref	Wird benutzt, um die Informationen der Herkunftswebsite des Benutzers zu speichern.	6 Monate	HTML	Matomo TU Wien
_pk_ses	Wird benötigt, um vorübergehende Daten des Besuchs zu speichern.	30 Minuten	HTML	Matomo TU Wien
nmstat	Wird benutzt, um das Verhalten auf der Website festzuhalten. Es wird genutzt, um Statistiken über die Websitenutzung zu sammeln, wie zum Beispiel wann der/die Besucher_in die Website zuletzt besucht hat. Das Cookie enthält keine personenbezogenen Daten und wird einzig für die Websiteanalyse eingesetzt.	1000 Tage	HTML	Siteimprove
siteimproveses	Wird dafür eingesetzt, um die Abfolge an Seiten zu verfolgen, die ein Besucher/eine Besucherin im Laufe des Besuchs auf der Website ansieht. Das Cookie enthält keine personenbezogenen Daten und wird einzig für die Websiteanalyse eingesetzt.	Session	HTTP	Siteimprove
AWSELB	Tritt immer paarweise mit siteimproveses auf (zur Lastverteilung am Anbieter-Server)	Session	HTTP	Siteimprove

Marketing

Mithilfe dieser Cookies und Drittanbieterinhalte sind wir bemüht, unser Angebot für Sie zu verbessern. Mittels pseudonymisierter Daten von Websitenutzern kann der Nutzerfluss analysiert und beurteilt werden. Dies gibt uns die Möglichkeit, Werbe- und Websiteinhalte zu optimieren.

Name	Zweck	Ablauf	Typ	Anbieter
_ga	Wird benötigt, um die Sessions der Benutzer_innen voneinander unterscheiden zu können.	Persistent	HTTP	Google Analytics
_gali	Wird benötigt, um festzustellen welche Links auf einer Seite angeklickt werden.	sofort	HTTP	Google Analytics
_gat	Dies ist ein funktionsbezogenes Cookie, dessen Aufgaben unterschiedlich sein können.	2 Jahre	HTTP	Google Analytics
_gid	Wird benötigt, um Benutzer_innen zu unterscheiden und Statistiken zu erstellen.	24 Stunden	HTTP	Google Analytics
_gads	Wird benötigt, um Websites zu ermöglichen Werbung von Google, einschließlich personalisierter Werbung, anzuzeigen.	13 Monate	HTTP	Google Analytics
_gac_	Wird von Werbetreibenden benötigt, um Nutzer_innenaktivitäten und die Leistung ihrer Werbekampagnen zu messen.	90 Tage	HTTP	Google Analytics
_gcl_	Wird von Werbetreibenden benötigt, um feststellen zu können, wie oft Nutzer_innen, die auf ihre Anzeigen klicken, am Ende eine Aktion auf ihrer Website ausführen.	90 Tage	HTTP	Google Analytics
_gcl_au	Enthält eine zufällig generierte Benutzer_innen-ID.	90 Tage	HTTP	Google
_gcl_aw	Wird gesetzt, wenn Nutzer_innen auf eine Google-Anzeige auf der Website klicken und enthält Informationen darüber, welche Anzeige angeklickt wurde.	90 Tage	HTTP	Google
__utma	Wird benötigt, um die Erfassung von Besuchen und Besucher_innen zu ermöglichen.	2 Jahre	HTTP	Google Analytics
__utmb	Wird benötigt, um neue Besuche zu erkennen.	30 Minuten	HTTP	Google Analytics
__utmc	Wird in Verbindung mit __utmb verwendet um festzustellen, ob es sich um einen neuen (kürzlichen) Besuch handelt.	Session	HTTP	Google Analytics
__utmd	Wird benötigt, um den Weg der Besucher_innen auf der Website zu speichern und zu verfolgen und sie in Gruppen zu klassifizieren (Marketing/Tracking).	1 Sekunde	HTTP	Google Analytics
__utmt	Wird benötigt, um die Abfragerate auf Google Analytics zu begrenzen.	10 Minuten	HTTP	Google Analytics
__utmz	Wird benötigt, um zu bestimmen aus welcher Quelle/Kampagne Besucher_innen kommen.	6 Monate	HTTP	Google Analytics
__utmvc	Wird benötigt, um Informationen über das Nutzer_innenverhalten auf mehreren Websites zu sammeln. Diese Informationen werden verwendet, um die Relevanz der Werbung auf der Website zu optimieren.	24 Stunden	HTTP	Google AdSense
utm_source	Wird benötigt, um URLs mit Parametern zu versehen, um die Kampagnen zu identifizieren, die den Verkehr weiterleiten.	sofort	HTTP	Google Analytics
__utm.gif	Wird zum Speichern von Browserdetails benötigt.	Session	HTTP	Google Analytics
gtag	Wird benötigt, um Remarketing zu betreiben.	30 Tage	HTTP	Google AdSense
id	Wird benötigt, um Remarketing zu betreiben.	2 Jahre	HTTP	Google AdWords
1P_JAR	Wird benötigt, um Werbung zu optimieren, für Nutzer_innen relevante Anzeigen bereitzustellen, Berichte zur Kampagnenleistung zu verbessern oder um zu vermeiden, dass Benutzer_innen dieselben Anzeigen mehrmals sehen.	2 Jahre	HTTP	Google
AID	Wird benötigt, um gezielte Werbung zu aktivieren.	2 Jahre	HTTP	Google Analytics
ANID	Wird benötigt, um Google-Werbung auf Websites einzublenden, die nicht zu Google gehören.	2 Jahre	HTTP	Google AdSense
APISID	Unbekannte Funktionalität	2 Jahre	HTTP	Google Ads Optimization
AR	Wird benötigt, um ein Profil der Interessen der Besucher_innen zu erstellen und relevante Werbung auf anderen Websites anzuzeigen. Dieses Cookie funktioniert, indem es Ihren Browser und Ihr Gerät eindeutig identifiziert.	2 Jahre	HTTP	Google AdSense
CONSENT	Wird benötigt, um die Vorlieben der Besucher_innen zu speichern und die Werbung zu personalisieren.	Persistent	HTTP	Google
DSID	Wird für Werbung benötigt, die an verschiedenen Stellen im Web angezeigt wird und dient zum Speichern der Präferenzen der Benutzer_innen.	2 Jahre	HTTP	Doubleclick
DV	Wird benötigt, um die Präferenzen der Nutzer_innen und andere Informationen zu speichern. Dazu gehören insbesondere die bevorzugte Sprache, die Anzahl der auf der Seite anzuzeigenden Suchergebnisse sowie die Entscheidung, ob der Google SafeSearch-Filter aktiviert werden soll oder nicht.	2 Jahre	HTTP	Google
HSID	Enthält die Google-Konto-ID und den letzten Anmeldezeitpunkt der Nutzer_innen.	2 Jahre	HTTP	Google
IDE	Wird benötigt, um die Handlungen der Benutzer_innen auf der Webseite nach der Anzeige oder dem Klicken auf eine der Anzeigen des Anbieters zu registrieren und zu melden, mit dem Zweck der Messung der Wirksamkeit einer Werbung und der Anzeige zielgerichteter Werbung für die Benutzer_innen.	2 Jahre	HTTP	Doubleclick
LOGIN_INFO	Wird benutzt, um die Anmeldedaten der Benutzer_innen von Google-Services zu speichern.	2 Jahre	HTTP	Google
NID	Wird benutzt, um Informationen über Nutzer_innen-Einstellungen zu speichern.	6 Monate	HTTP	Google
OTZ	Wird benötigt, um Aktivitäten von Besucher_innen mit anderen Geräten, die zuvor über das Google-Konto eingeloggt sind zu verknüpfen. Auf diese Weise wird die Werbung auf verschiedene Geräte zugeschnitten.	1 Monat	HTTP	Google
RUL	Wird benötigt, um festzustellen, ob Werbung richtig angezeigt wurde, um Marketingaktivitäten effizienter zu gestalten.	1 Jahr	HTTP	Doubleclick
SAPISID	Wird benötigt, um Benutzer_innen-Einstellungen zu speichern und um die Bandbreite der User_innen zu berechnen.	Persistent	HTTP	Google
SEARCH_SAMESITE	Ermöglicht es Servern, das Risiko von CSRF- und Informationsleck-Angriffen zu mindern, indem es festlegt, dass ein bestimmtes Cookie nur bei Anfragen gesendet werden darf, die von derselben registrierbaren Domäne ausgehen.	6 Monate	HTTP	Google
SID	Enthält die Google-Konto-ID und den letzten Anmeldezeitpunkt der Nutzer_innen.	2 Jahre	HTTP	Google
SIDCC	Wird benötigt, um Informationen über Nutzer_inneneinstellungen und -informationen für Google Maps zu speichern.	3 Monate	HTTP	Google
SSID	Wird benötigt, um Besucher_innen Informationen für Videos, die von YouTube auf in Google Maps integrierten Karten gehostet werden zu sammeln.	Persistent	HTTP	Google
__SECURE-1PAPISID	Wird für Targeting-Zwecke benötigt, um ein Profil der Interessen der Website-Besucher_innen zu erstellen.	2 Jahre	HTTP	Google
__SECURE-1PSID	Wird für Targeting-Zwecke benötigt, um ein Profil der Interessen der Website-Besucher_innen zu erstellen.	2 Jahre	HTTP	Google
__SECURE-3PAPISID	Wird für Targeting-Zwecke benötigt, um ein Profil der Interessen der Website-Besucher_innen zu erstellen.	2 Jahre	HTTP	Google
__SECURE-3PSID	Wird für Targeting-Zwecke benötigt, um ein Profil der Interessen der Website-Besucher_innen zu erstellen.	2 Jahre	HTTP	Google
__SECURE-3PSIDCC	Wird für Targeting-Zwecke benötigt, um ein Profil der Interessen der Website-Besucher_innen zu erstellen.	2 Jahre	HTTP	Google
__SECURE-APISID	Wird benötigt, um ein Profil der Interessen von Website-Besucher_innen zu erstellen, um durch Retargeting relevante und personalisierte Werbung anzuzeigen.	8 Monate	HTTP	Google
__SECURE-HSID	Wird benötigt, um digital signierte und verschlüsselte Daten aus der eindeutigen Google-ID zu sichern und die letzte Anmeldezeit, die Google zur Identifizierung von Besucher_innen, zur Verhinderung der betrügerischen Verwendung von Anmeldedaten und zum Schutz von Besucher_innendaten von unbefugten Parteien zu speichern. Dies kann auch für Targeting-Zwecke verwendet werden, um relevante und personalisierte Werbeinhalte anzuzeigen.	8 Monate	HTTP	Google
__SECURE-SSID	Wird benötigt, um Informationen darüber zu speichern, wie die Besucher_innen die Website nutzen, und über die Anzeigen, die sie möglicherweise gesehen haben, bevor sie die Website besucht haben. Wird auch zur Anpassung von Anzeigen auf Google-Domains verwendet.	8 Monate	HTTP	Google
test_cookie	Wird als Test gesetzt, um zu prüfen, ob der Browser das Setzen von Cookies zulässt. Enthält keine Identifikationsmerkmale.	15 Minuten	HTTP	Google
VISITOR_INFO1_LIVE	Wird benötigt, um Benutzer_innen-Einstellungen zu speichern und um die Bandbreite der User_innen zu berechnen.	6 Monate	HTTP	Youtube
facebook	Wird verwendet, um Anzeigen auszuliefern oder Retargeting zu ermöglichen	90 Tage	HTTP	Meta (Facebook)
__fb_chat_plugin	Wird zum Speichern und Verfolgen von Interaktionen (Marketing/Tracking) benötigt.	Persistent	HTTP	Meta (Facebook)
_js_datr	Wird benötigt, um Benutzer_inneneinstellungen zu speichern.	2 Jahre	HTTP	Meta (Facebook)
_fbc	Wird benötigt, um den letzten Besuch zu speichern (Marketing/Tracking).	2 Jahre	HTTP	Meta (Facebook)
fbm	Wird benötigt, um Kontodaten zu speichern (Marketing/Tracking).	1 Jahr	HTTP	Meta (Facebook)
xs	Wird zum Speichern einer eindeutigen Sitzungs-ID benötigt (Marketing/Tracking).	1 Jahr	HTTP	Meta (Facebook)
wd	Wird benötigt, um die Bildschirmauflösung zu loggen.	1 Woche	HTTP	Meta (Facebook)
fr	Wird benötigt, um Anzeigen zu schalten und deren Relevanz zu messen und zu verbessern.	3 Monate	HTTP	Meta (Facebook)
act	Wird benötigt, um angemeldete Benutzer_innen zu speichern (Marketing/Tracking).	90 Tage	HTTP	Meta (Facebook)
_fbp	Wird zum Speichern und Verfolgen von Besuchen auf verschiedenen Websites benötigt (Marketing/Tracking).	3 Monate	HTTP	Meta (Facebook)
datr	Wird benötigt, um den Browser für Sicherheits- und Website-Integritätszwecke, einschließlich der Wiederherstellung von Konten und der Identifizierung von potenziell gefährdeten Konten zu identifizieren.	2 Jahre	HTTP	Meta (Facebook)
dpr	Wird für Analysezwecke verwendet. Technische Parameter werden protokolliert (z. B. Seitenverhältnis und Abmessungen des Bildschirms), damit Facebook-Apps korrekt angezeigt werden können.	1 Woche	HTTP	Meta (Facebook)
sb	Wird benötigt, um Browserdetails und Sicherheitsinformationen des Facebook-Kontos zu speichern.	2 Jahre	HTTP	Meta (Facebook)
dbln	Wird benötigt, um Browserdetails und Sicherheitsinformationen des Facebook-Kontos zu speichern.	2 Jahre	HTTP	Meta (Facebook)
spin	Wird für Werbezwecke und Berichterstattung über soziale Kampagnen benötigt.	Session	HTTP	Meta (Facebook)
presence	Enthält den "Chat"-Status eingeloggter Benutzer_innen.	1 Monat	HTTP	Meta (Facebook)
cppo	Wird für statistische Zwecke benötigt.	90 Tage	HTTP	Meta (Facebook)
locale	Wird benötigt, um die Spracheinstellungen zu speichern.	Session	HTTP	Meta (Facebook)
pl	Wird für Facebook Pixel benötigt.	2 Jahre	HTTP	Meta (Facebook)
lu	Wird für Facebook Pixel benötigt.	2 Jahre	HTTP	Meta (Facebook)
c_user	Wird für Facebook Pixel benötigt.	3 Monate	HTTP	Meta (Facebook)
bcookie	Wird zur Speicherung von Browserdaten benötigt (Marketing/Tracking).	2 Jahre	HTTP	LinkedIn
li_oatml	Wird verwendet, um LinkedIn-Mitglieder außerhalb von LinkedIn zu Werbe- und Analysezwecken zu identifizieren.	1 Monat	HTTP	LinkedIn
BizographicsOptOut	Wird zum Speichern von Datenschutzeinstellungen benötigt.	10 Jahre	HTTP	LinkedIn
li_sugr	Wird zur Speicherung von Browserdaten benötigt (Marketing/Tracking).	3 Monate	HTTP	LinkedIn
UserMatchHistory	Wird zur Bereitstellung von Werbeeinblendungen oder Retargeting benötigt (Marketing/Tracking).	30 Tage	HTTP	LinkedIn
linkedin_oauth_	Wird benötigt, um seitenübergreifende Funktionen bereitzustellen.	Session	HTTP	LinkedIn
lidc	Wird benötigt, um durchgeführte Aktionen auf der Website zu speichern (Marketing/Tracking).	1 Tag	HTTP	LinkedIn
bscookie	Wird benötigt, um durchgeführte Aktionen auf der Website zu speichern (Marketing/Tracking).	2 Jahre	HTTP	LinkedIn
X-LI-IDC	Wird benötigt, um seitenübergreifende Funktionen bereitzustellen (Marketing/Tracking).	Session	HTTP	LinkedIn
AnalyticsSyncHistory	Speichert den Zeitpunkt, zu dem der/die Benutzer_in mit dem "lms_analytics"-Cookie synchronisiert wurde.	30 Tage	HTTP	LinkedIn
lms_ads	Wird benötigt, um LinkedIn-Mitglieder außerhalb von LinkedIn zu identifizieren.	30 Tage	HTTP	LinkedIn
lms_analytics	Wird benötigt, um LinkedIn-Mitglieder zu Analysezwecken zu identifizieren.	30 Tage	HTTP	LinkedIn
li_fat_id	Wird für eine indirekte Mitgliederidentifikation benötigt, die für Conversion Tracking, Retargeting und Analysen verwendet wird.	30 Tage	HTTP	LinkedIn
U	Wird benötigt, um den Browser zu identifizieren.	3 Monate	HTTP	LinkedIn
_guid	Wird benötigt, um ein LinkedIn-Mitglied für Werbung über Google Ads zu identifizieren.	90 Tage	HTTP	LinkedIn