KomplexitĂ€t #12: 3SAT ist NP-hart đ§©
Analyse der NP-HĂ€rte von 3SAT, inklusive Reduktion, Korrektheit und Laufzeitanalyse. Relevanz fĂŒr KomplexitĂ€tstheorie.
NLogSpace
13.7K views âą Jun 10, 2018
About this video
0:00 Einleitung
2:24 Beschreibung der Reduktion
14:50 Korrektheit
16:17 Laufzeitanalyse
17:29 Relevanz von 3SAT
Wir sehen uns eine Polyzeit-Many-One-Reduktion von SAT auf 3SAT an und zeigen damit, dass 3SAT NP-hart ist. Da 3SAT auch in NP ist, haben wir hiermit ein weiteres NP-vollstÀndiges Problem gefunden. 3SAT eignet sich besonders gut als Ausgangspunkt, um von weiteren Problemen NP-HÀrte nachzuweisen.
2:24 Beschreibung der Reduktion
14:50 Korrektheit
16:17 Laufzeitanalyse
17:29 Relevanz von 3SAT
Wir sehen uns eine Polyzeit-Many-One-Reduktion von SAT auf 3SAT an und zeigen damit, dass 3SAT NP-hart ist. Da 3SAT auch in NP ist, haben wir hiermit ein weiteres NP-vollstÀndiges Problem gefunden. 3SAT eignet sich besonders gut als Ausgangspunkt, um von weiteren Problemen NP-HÀrte nachzuweisen.
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
13.7K
Likes
260
Duration
18:52
Published
Jun 10, 2018
User Reviews
4.6
(2) Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.
Trending Now