6.3Komplexitätstheorie

P = NP?

Ist Finden so leicht wie Prüfen? Die wichtigste offene Frage der Informatik – und was Quantencomputer daran ändern.

Leitformel
P⊆NP⊆PSPACE=NPSPACE⊆EXP\mathrm P \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} = \mathrm{NPSPACE} \subseteq \mathrm{EXP}
P⊆NP⊆PSPACE\mathrm P \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE}=NPSPACE⊆EXP= \mathrm{NPSPACE} \subseteq \mathrm{EXP}
Lernziel

Die Klassen P, NP, PSPACE und EXP einordnen, polynomiale Reduktionen und NP-Vollständigkeit erklären und die Rolle von SAT und Quantenalgorithmen verstehen.

Einheit wird geladen …