GrundkursTheoretische Informatik, Folie 11.1 © 2004 G. Vossen,K.-U. Witt

Grundkurs Theoretische Informatik

Kapitel 11

Gottfried VossenGottfried VossenKurt-Ulrich WittKurt-Ulrich Witt

GrundkursTheoretische Informatik, Folie 11.2 © 2004 G. Vossen,K.-U. Witt

Komplexität

Die O-NotationKomplexität von AlgorithmenWichtige KomplexitätsklassenDie Klassen P und NPKonkrete NP-vollständige ProblemeWeitere KomplexitätsklassenZusammenfassung

GrundkursTheoretische Informatik, Folie 11.3 © 2004 G. Vossen,K.-U. Witt

NP-vollständige Probleme und die Klassen P und NP

GrundkursTheoretische Informatik, Folie 11.4 © 2004 G. Vossen,K.-U. Witt

Zusammenhang zwischen Komplexitätsklassen

Entscheidbare Probleme

EXPTIME

PSPACE = NPSPACE

NP coNP

P CONPCNPC

GrundkursTheoretische Informatik, Folie 11.5 © 2004 G. Vossen,K.-U. Witt

Ende Kapitel 11Ende Kapitel 11