Entscheidungsprobleme < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:01 So 20.04.2008 | | Autor: | balboa |
| Aufgabe | Für drei Entscheidungsprobleme [mm]L_A, L_B und L_C[/mm] sei ein Algorithmus A, B, C gegeben, der für eine Eingabezahl [mm]x \in N[/mm] entscheidet, ob [mm]bin(x) \in L_A, bin(x) \in L_B bzw. bin(x) \in L_C[/mm] ist. Von diesen Algorithmen sind nur die folgenden Eigenschaften bekannt:
A: Algorithmus A terminiert immer nach [mm]O(log x)[/mm] Schritten. Für [mm]bin(x) \in L_A[/mm] akzeptiert A mit einer Wahrscheinlichkeit von min. [mm]\bruch{3}{4}[/mm] für [mm]bin(x) \not\in L_A[/mm] verwirft A mit einer Wahrscheinlichkeit von min. [mm]\bruch{3}{4}[/mm].
B: Wenn [mm]bin(x) \in L_B[/mm], so akzeptiert Algorithmus B mit Wahrscheinlichkeit 1 in Zeit [mm]O(log x)[/mm]. Wenn [mm]bin \not\in L_B[/mm], so verwirft B mit Wahrscheinlichkeit von min. [mm]\bruch{2}{3}[/mm] in Zeit [mm]O(log x)[[/mm]
C: Der Algorithmus C terminiert nach [mm]O(x)[/mm] Schritten. Die Ausgabe ist immer mit einer Wahrscheinlichkeit von genau [mm]\bruch{3}{5}[/mm] korrekt.
Ordne die Entscheidungsprobleme den Komplexitätsklassen zu, begründe. |
Ich stehe vor einem absoluten Rätsel und bin auf eure Hilfe angewiesen. Danke!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:21 Mi 23.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
