Ein Optimierungsproblem besteht aus einer Menge
von Lösungen und einer Zielfunktion
, die jeder Lösung einen Wert (Qualität; Fitness) zuordnet. Im Fall eines Maximierungsproblems ist
umso höher, je besser die Lösung
ist. Bei einem Minimierungsproblem ist es umgekehrt, was sich durch Negieren von
auf den ersten Fall zurückführen lässt. Man sucht in der Regel eine beste (optimale) Lösung in
, also ein
mit dem höchsten bzw. niedrigsten
.
Man unterscheidet hier folgende Problemstellungen:
- Entscheidungsprobleme, bei denen zusätzlich ein Grenzwert
gegeben ist, und ermittelt werden soll, ob es ein
gibt mit
.
- eigentliche Optimierungsprobleme, bei denen man den Wert der besten Lösung wissen will, also
.
- Suchprobleme, bei denen eine optimale Lösung
gesucht ist, also
, oder eine Lösung mit einer gegebenen Mindestqualität, d. h. ein
mit
.
- Approximationsprobleme: man will eine möglichst gute Lösung finden, ohne dass von vornherein weitere Vorgaben gemacht werden.
In der Theoretischen Informatik meint man mit Optimierungsproblem in der Regel ein eigentliches Optimierungsproblem, bei dem also nur der bestmögliche Wert und keine Lösung selbst gesucht ist. Auch betrachtet man üblicherweise den Sonderfall einer diskreten Bewertungsfunktion
, da dies meist keinen erheblichen Unterschied macht und man reelle Zahlen weniger gut handhaben kann, z. B. näherungsweise als Gleitkommazahlen.
Meistens betrachtet man in der Theoretischen Informatik aber Entscheidungsprobleme. Zu einem Optimierungsproblem lässt sich leicht ein Entscheidungsproblem erzeugen, indem man zur Problemstellung den Grenzwert
bzw.
hinzunimmt. Umgekehrt kann man für die meisten praktisch interessanten Probleme zeigen, dass ein Lösungsweg für das Entscheidungsproblem zu einer Lösung des entsprechenden Such- oder Optimierungsproblems modifiziert werden kann, die nicht entscheidend mehr Rechenzeit oder Speicherplatz benötigt.
Gesucht:
, welches das größte
liefert.
Befehlssatz
endliches Alphabet
mit
Operatoren
surjektive Adressfunktion:
Programm
Register
Die Maschine beginnt mit
mit der Eingabe in den Registern
bis
mit
. Ein Arbeitsschritt besteht in der Ausführung des Befehls
gemäß nachfolgender Tabelle. Dies wird iterativ wiederholt, solange
(Der Index 1 bedeutet: das erste Element des Tupels
). Wenn
, hält die Maschine an, und die Ausgabe steht in den Registern.
Alternativ: zur Befehlsmenge werden
zum Lesen der Eingabe bzw. Schreiben in die Ausgabe hinzugefügt, und alle Register werden mit
initialisiert.
![{\displaystyle P(p)_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a353775212f2bbebfbe14f69df52ed98516a26e2) |
Aktion
|
aset |
|
rset |
|
rinc |
|
j |
|
jB |
wenn dann
|
jnB |
wenn dann
|
ld |
|
st |
|
op(i) |
|
ild |
|
ist |
|
iop(i) |
|
in |
nächstes Eingabezeichen
|
out |
Ausgabe
|
Nach jeder Aktion wird der Befehlszähler inkrementiert (
), außer nach einem Sprung, d. h. nachdem
ausgeführt wurde.
Für die Befehle ild, ist und iop(1) bis iop(x) wird die Adresse A wie folgt berechnet:
![{\displaystyle A\leftarrow 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8e000f05751897ebec6004268881cbac8ce7dcc)
![{\displaystyle j\leftarrow r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11e6525733002938dff2b1da741a9fba12ed1b9a)
- while
do
![{\displaystyle A\leftarrow \alpha \cdot A+g(R(j))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eedf443ee76521fff25099ed3be6d1ef3c0bc044)
![{\displaystyle j\leftarrow j+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5a5e3291b445ad105c3e4d7c5c58057196074c7)
- end while
- endliches Arbeitsalphabet
mit ![{\displaystyle \gamma _{0}\in \Gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8892e58951da16c37b971a3f5c6525d7753a0a82)
- Programm
![{\displaystyle P:\mathbb {Z} \rightarrow C\times \Gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/433cf7a45cb87ac66c69d454dc8743f37987baab)
- Register
![{\displaystyle R:\mathbb {Z} \rightarrow \Gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/060efe0caf7034a767c9b5ab656ded5023dc29b6)
- Akkumulator
![{\displaystyle a\in \Gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ab910d60424971a3e4723d4646e5b1b2a81159a)
- Befehlszähler
![{\displaystyle c\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8d2be34156860619e6114c8fde955043a405af5)
- Addressregister
![{\displaystyle p\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d29b9c8775da833d554991bfefdfc54a53085728)
- Operatoren
![{\displaystyle f_{i}:\Gamma \times \Gamma \rightarrow \Gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/834d5da9fd3246fb549d03e25c77a8ddf9492b3b)
- Prädikate
![{\displaystyle g_{i}:\Gamma \rightarrow \{wahr,falsch\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e92400f052b8b4d0e3304737559d5be7e1c3df48)
- surjektive Addressfunktion
![{\displaystyle h:\Gamma \rightarrow \{z\in \mathbb {Z} \;|\,-\lfloor |\Gamma |/2\rfloor \leq z<\lceil |\Gamma |/2\rceil \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/215d55165534d13d3fe5375d828d326b0cf2c6fc)
Befehlscode ![{\displaystyle P(c)_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/654bddc27706a6b313b816b680f1db07cf53f642) |
Aktion
|
set |
|
load |
|
op(i) |
|
store |
|
jmp(i) |
wenn , dann , sonst
|
offs |
|
halt |
(keine)
|
Am Anfang ist
und
.
Das Programm der Länge
steht in
, und es ist
für
oder
.
Die Eingabe der Länge
steht in
, und es ist
für
oder
.
. Gegeben: Verkettungsfunktion
, Nachricht
, Salz
mit
, Hashlänge
.
![{\displaystyle M\,\|\,0^{j}=M_{1}\,\|\,M_{2}\,\|\,\dots \,\|\,M_{k};\quad |M_{i}|=r,\,j<r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fa414c727ccfb67cbc9deaf6f4a70a1f503dfff)
![{\displaystyle h_{0}=f(e,S\,\|\,0^{r-n},0,n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/add31919f5dd0c47d099e7491e7151135c101da1)
![{\displaystyle h_{i}=f(h_{i-1},M_{i},i,g(i));\quad i=1,\dots ,k;\quad g(i)={\begin{cases}0&{\text{wenn }}i<k\\r-j&{\text{wenn }}i=k\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e23a231686acdb72759812d8db17b8b781b6b71a)
![{\displaystyle hash=\operatorname {trunc} (h_{k},e)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d073b36a00cef9cc048d4cacbae2bb9451387f2a)
Notation:
ist die Menge der natürlichen Zahlen mit Null.
ist das Alphabet einer formalen Sprache, das heißt jedes Wort ist eine binäre Zeichenfolge bestehend aus
und
.
bezeichnet die Menge aller binären Wörter der Länge
.
bezeichnet die Menge aller endlich langen binären Wörter.
Ein Entscheidungsproblem wird als formale Sprache
über dem Alphabet
dargestellt, also
. Dazu wird ein Formalismus festgelegt, um jede Probleminstanz (deren Lösung eine ja/nein-Antwort ist) als Wort in
darzustellen, und
enthält genau die Wörter
, die eine gültige Darstelung einer Probleminstanz sind, auf die die richtige Antwort „ja“ lautet.
bezeichne die Menge der Algorithmen
, die das Problem
lösen:
.
bezeichnet die Zahl der Rechenschritte, die der Algorithmus
bei Eingabe von
ausführt, mit der Turingmaschine als ausführendes Maschinenmodell.
Die Klasse
ist die Menge der effizient-lösbaren Entscheidungsprobleme. Ein Entscheidungsproblem
ist effizient-lösbar, falls ein Algorithmus
existiert, der nur polynomielle Zeit braucht, d. h. es existiert ein Polynom
, so dass
.
Dann ist
die Klasse der effizient-lösbaren Entscheidungsprobleme, das heißt[1]
![{\displaystyle \mathbf {P} =\{S\;|\;\exists A:\forall x:(A(x)=1\iff x\in S)\wedge t(A,x)<=p\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7509ef569b66f0ed4b60e32a615cae4916e7ac18)
- ↑ Oded Goldreich: P, NP, and NP-Completeness: The Basics of Computational Complexity. Hrsg.: Cambridge University Press. 2010, ISBN 978-0-521-19248-4 (englisch).