Video
Not enough ratings.
Reduktion und Vollständigkeit 3/3
1
13
34
185
350
440
646
845
1020
1673
1674
1677
1872
2045
2066
2194
2285
2288
2327
2616
2802
2989
3023
3025
3114
3515
3657
3827
4018
4086
4355
4489
Lecture Structure
- Berechnungstabellen Methode (1 (00:35:53)
- Berechnungstabellen Methode (F (00:34:14)
- Berechnungstabellen Methode ( (00:33:31)
- Berechnungstabellen Methocle ( (00:30:35)
- Ist Lesekopfder TM im i ten Schritt an Position j (00:30:35)
- 1 Band TM simuliert werden können (00:30:35)
- Betrachten lediglich 1 Band TM (00:30:35)
- Zur Vereinfachung wird Berechnungstabelle standardisiert (1 2) (00:30:35)
- K vo srana gke r (5 5) (00:15:40)
- ann gilt K (00:15:40)
- K vollständig ist c (00:15:40)
- Satz (00:15:40)
- Korollar2 Sei A NP vollständig (00:15:40)
- K vo srana gke r (4 5) (00:13:29)
- K vo srana gke r (3 5) (00:10:02)
- K vo sräna gke r (2 5) (00:06:34)
- K vo sranc gke r (1 5) (00:04:07)
- A heißt vollständigin K bzw K vollständig wenn für alle (00:04:07)
- Können nun Frage stellen nach den schwersten Problemen in (00:04:07)
- Einführung (00:02:28)
- Vorlesungen zur Komplexitätstheorie (00:00:13)
- WE Reduktion und Vollständigkeit (3) (00:00:13)
- Konzepte der Kom plexitätstheorie (00:00:13)
- Vorlesungsprogramm (00:00:13)
- Ijlasso Plattner (00:00:01)
- Berechnungstabellen Methode ( (00:22:18)
- ezeichnung Berechnungstabelle T (00:22:18)
- NP Vollständigkeit ist die Berechnungstabellen Methode (00:22:18)
- Beispiel (00:27:53)
- Berechnungstabellen Methode ( (ZXGZ (00:27:54)
- P Vollständigkeit von CIRCUIT VALUE (1 10) (00:37:31)
- P Vollständigkeit von CIRCUIT VALUE (2 10) (00:38:05)
- P Vollständigkeit von CIRCUIT VALU E (1 10) (00:38:08)
- P Vollständigkeit von CIRCUIT VALUE (2 10) (00:42:46)
- P Vollständigkeit von CIRCUIT VALUE (3 10) (00:45:02)
- gibt Bandinhalt an j ter Stelle im i ten Takt an (00:45:02)
- Beweisen A309 CIRCUITVALUE(Z 9) (00:45:02)
- P Vollständigkeit von CIRCUIT VALUE (4 10) (00:49:48)
- Erhalten so eine Tabelle mit den binären Eingängen (00:49:48)
- Beweisen A309 CIRCUITVALUE(3 9) (00:49:48)
- Erhalten so eine Tabell mif Ü nvl näfen ing ngen (00:49:49)
- als Vektoren (rl rm (00:49:49)
- Kodieren (00:49:49)
- Erhalten so eine Tabell mit H nvlf näfen ingängen (00:50:25)
- Menge aller möglichen Tabßllensymbole (00:50:25)
- P Vollständigkeit von CIRCUIT VALUE (5 10) (00:54:16)
- P Vollständigkeit von CIRCUIT VALUE (6 10) (00:59:13)
- binäre Kodierung von (00:59:13)
- für jedes (00:59:13)
- werden kann existiert ein Schaltkreise C (00:59:13)
- Da jede Boolesche Funktion durch einen Schaltkreis berechnet (00:59:13)
- P Vollständigkeit von CIRCUIT VALUE (7 10) (01:02:52)
- Eingaben der Schaltkreise der ersten Reihe und der ersten und (01:02:52)
- sind die Ausgaben von (01:02:52)
- Eingaben für (01:02:52)
- Fürjedes x besteht R(x) aus ( (01:02:52)
- Konstruieren nun die Reduktion (01:02:52)
- Die SchaltkreiseC hängen nur von M ab und haben eine (01:02:52)
- Beweisen A 5 09 CIRCUIT VALUE (6 9) (01:02:52)
- P Vollständigkeit von CIRCUIT VALUE (8 10) (01:06:43)
- gilt daß (01:06:43)
- Sei nun R(x) = true (01:06:43)
- Können durch InduI tion zeigen daß Ausgaben der Schaltkreise C (01:06:43)
- Beweisen A 5 09 CIRCUIT VALUE (7 9) (01:06:43)
- P Vollständigkeit von CIRCUIT VALUE (9 10) (01:07:52)
- Bleibt noch zu zeigen (01:07:52)
- Alsogilt R(x) istwahr ( ) x (01:07:52)
- Behauptung( ) Z z Gilt x A dann ist R(x) Wahr (01:07:52)
- Beweisen A 5 09 CIRCUIT VALUE (8 9) (01:07:52)
- P Vollständigkeit von CIRCUIT VALUE (10 10) (01:10:27)
- (1) Konstruktion der Input Gatter ist leichtvmögltfh durch (01:10:27)
- Die Berechnung von R(x) e fordert (01:10:27)
- Behauptung R(x) kann mit Speicherplatz log x berechnet (01:10:27)
- P Vollständigkeit von MONTONE CIRCUIT VALUE (01:13:58)
- Ijlasso Plattner (01:15:28)
Links added to this content
No links have been added to this content so far.
Tags added to this content
No tags have been added to this content so far.
Create Note
Dear user,
with the manuscript function you'll be able to create your own digital lecture manuscript.
However, in order to link all your notes with your user profile it is required that you
login to the tele-TASK portal to use this functionality.
If you don't have an account yet, you may register for a tele-TASK account here.
with the manuscript function you'll be able to create your own digital lecture manuscript.
However, in order to link all your notes with your user profile it is required that you
login to the tele-TASK portal to use this functionality.
If you don't have an account yet, you may register for a tele-TASK account here.
Place a Marker
Dear user,
with the marker function you'll be able to create your own digital time markers.
However, in order to link all your markers with your user profile it is required that you
login to the tele-TASK portal to use this functionality.
If you don't have an account yet, you may register for a tele-TASK account here.
with the marker function you'll be able to create your own digital time markers.
However, in order to link all your markers with your user profile it is required that you
login to the tele-TASK portal to use this functionality.
If you don't have an account yet, you may register for a tele-TASK account here.
Please enable javascript to use this function.
Keyword
Please enable javascript to use this function.
Add to my playlist
Dear user,
with the playlist function you'll be able to create your own lecture video playlists.
However, in order to link all your playlists with your user profile it is required that you
login to the tele-TASK portal to use this functionality.
If you don't have an account yet, you may register for a tele-TASK account here.
with the playlist function you'll be able to create your own lecture video playlists.
However, in order to link all your playlists with your user profile it is required that you
login to the tele-TASK portal to use this functionality.
If you don't have an account yet, you may register for a tele-TASK account here.
Playlists
This content is not used in any playlist.