Komplexität #15 - 3-Färbbarkeit ist NP-hart
0:00 3COL 0:52 Reduktion 9:40 Korrektheit 11:59 Polyzeit Wir sehen uns eine Reduktion von 3SAT auf 3-Färbbarkeit (3COL) an. Wir haben bereits in Video #7 ge...
NLogSpace
10.1K views • Jun 22, 2018
About this video
0:00 3COL
0:52 Reduktion
9:40 Korrektheit
11:59 Polyzeit
Wir sehen uns eine Reduktion von 3SAT auf 3-Färbbarkeit (3COL) an. Wir haben bereits in Video #7 gesehen, dass 3COL in NP ist, d.h. es folgt nun daraus, dass 3COL NP-vollständig ist.
0:52 Reduktion
9:40 Korrektheit
11:59 Polyzeit
Wir sehen uns eine Reduktion von 3SAT auf 3-Färbbarkeit (3COL) an. Wir haben bereits in Video #7 gesehen, dass 3COL in NP ist, d.h. es folgt nun daraus, dass 3COL NP-vollständig ist.
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
10.1K
Likes
210
Duration
13:48
Published
Jun 22, 2018
User Reviews
4.6
(2) Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.
Trending Now