Informatik

1.140 Mitglieder, 5.051 Beiträge

NP-Vollständig. Wie zeigen das Problem in NP-schwer liegt.?

Wenn man zeigen will, das ein Problem A NP-vollständig ist müssen 2 Bedingungen erfüllt sein: A muss Element von NP sein und A muss NP schwierig sein. Sieht man ja in der Grafik. Ist hier die angegebene Reduktion A <= B(NP-schwer) richtig oder falsch? B wäre somit mindestens so schwierig wie A und A ist maximal so schwierig wie B(NP-schwer), somit weiß man ja nicht sicher ob A in NP-schwer liegt. A ist maximal so schwierig... Oder müsste es per Reduktion B(NP-schwer) <= A sein, damit A sicher Element von NP-schwer ist. A ist mindestens so schwierig wie B(NP-schwer) B(NP-schwer) ist maximal so schwierig wie A. Des macht keinen Sinn.
Bild zum Beitrag

EBNF aufgabe?

Hi wir hatten heute dies aufgabe könnt ihr das lösen ? Aufgabe 6: EBNF aus Vorgaben erstellen Erstellt EBNF-Regeln aus den folgenden Vorgaben: 1. Ein Haus besteht aus vier Außenwänden einer Tür und einem Dach. 2. Außerdem kann es optional (beliebig viele)Innenwände, (beliebig viele) Fenster und einen Garten erhalten. 3. Das Dach besteht aus beliebig vielen Dachziegeln, optionalen (beliebig vielen) Dachfen- stern und einem optionalen Schornstein. 4. Ein Garten besteht aus beliebig vielen Blumen und Kräutern. Was sind die Token und die Nichtterminalen Symbole dieser Grammatik