    
Shan22 (Shan22)
Erfahrenes Mitglied
Benutzername: Shan22
Nummer des Beitrags: 55
Registriert: 12-2003
| | Veröffentlicht am Mittwoch, den 27. April, 2005 - 08:26: | 
|
hallo, villeicht jemand wie man diese aufgabe löst, dich ich sehr schwer finde!??!
Seien L1 und L2 Entscheidungsprobleme aus BPP(1=6). Sei L das Entscheidungsproblem
mit x Elem. L <=> x Elem. L1 und x Elem. L2 (also L = L1 geschnitten L2). Zeige zunächst, dass
es einen BPP(1/3)-Algorithmus gibt, der L entscheidet. Begründe anschliessend, dass BPP
gegen Durchschnitt abgeschlossen ist, also dass aus L1; L2 Elem. BPP schon L Elem. BPP folgt. |
