VL-13: Polynomielle Reduktionen Flashcards
(4 cards)
1
Q
Was ist die EXPTIME Klasse?
A
EXPTIME ist die Klasse an Entscheidungsproblemen, die in exponentiereller Zeit von einer TM berechnet werden können.
2
Q
Was ist ein Optimierungsproblem?
A
Ein Optimierungsproblem defeniert als Eingabe ein Lösungsmenge L, sowie eine Kosten-/ Profitfunktion L → N.
Das Ziel ist es die Kosten zu minimieren (Minimierungsproblem) oder den Profit zu maximieren (Maximierungsproblem)
3
Q
Wie funktioniert polynomielle Reduktion?
A
Es gibt einen polynomiell beschränkten Algorithmus f, für den gilt:
x in L1 g.d.w. f(x) in L2
4
Q
A
