Ψ Die Informatikseite
Menü
Bachelorstudium
- Lineare Algebra
- Algorithmen
- Theoretische Informatik
Masterstudium
- Neuronale Netze
- Computeranimation
Bonusmaterial
- Textsatz mit Latex
- Tipps und Tricks zu PDF-Dateien
- Einplatinenrechner
Studentenratgeber
Studienorte
Bücher
Impressum
Menü
Bachelorstudium
Lineare Algebra
Algorithmen
Theoretische Informatik
Masterstudium
Neuronale Netze
Computeranimation
Bonusmaterial
Textsatz mit Latex
Tipps und Tricks zu PDF-Dateien
Einplatinenrechner
Studentenratgeber
Studienorte
Bücher
Impressum
Informatik
»
Bachelor
»
Theoretische Informatik
»
NPC Beweise
Platzkomplexität
Theoretische Informatik
Die große Frage der Informatiker P=NP oder P≠NP?
NPC Beweise
Unterabschnitte
Die große Frage der Informatiker P=NP oder P
NP?
Polynomielle Reduzierbarkeit
NP-hart, NP-vollständig
NP-hart
NP-vollständig
Sätze
Aussagelogik
Satz von Cook
Satz
Beweis
Korrektheit
Kosten
Prinzipielle Techniken für NP-Vollständigkeitsbeweise
Spezialisierung
Lokale Ersetzung
Transformation mit verbundenen Komponenten
Einige NP-Vollständigkeitsbeweise
SAT
3SAT (lokale Ersetzung)
3SAT
CP (Transformation)
3SAT
RP (Transformation sowie auch Spezialisierung)
0/1 Integer Linear Programming (Transformation)
Weitere NPC-Beweise
coNP
PSPACE-Vollständigkeit
Zusammenfassung
Platzkomplexität
Theoretische Informatik
Die große Frage der Informatiker P=NP oder P≠NP?