Vorbereitungsblatt 9

Quadrupel P = (I,s,m,t)

I = x Werte

s = s(x) -> bildet x aus I auf Menge möglicher Lösungen ab

m = m(x,y)-> Wert von y zu x Maßfunktion, y Element von s(x)

t => {min oder max}

Entscheidungsproblem ist

Eingabe diesmal mit Ziel (K) und abhängig von min oder max soll optimale Lösung kleiner oder größer als K sein

Wenn Optimierungsproblem in NPO liegt, dann liegt das dazugehörige Entscheidungsproblem in NP

liegt in P, wenn Problem in NP(normal,schwer,vollständig) liegt

Wenn das zugehörige Entscheidungsproblem NP-vollständig ist muss das Optimierungsproblem NP-schwer sein und damit nicht Teil von PO