Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in 2009-H-04

Spalte 3- Zeile 3&4

Thu, 21 Jul 2016 08:07:17 +0000

Guten morgen,

ich bitte um Nachsicht, wenn ich mich aufgrund Unverständnis nochmals auf Spalte 3, Zeile 3&4 beziehe. Wäre es möglich, dass Jemand nochmals versucht zu erklären, weshalb an erwähnten Stellen kein Kreuz gesetzt wird? Zusätzlich wäre es sehr hilfreich, wenn die Aussage "selbe Klasse lässt sich nicht im Allgemeinen auf die selbe Klasse reduzieren" etwas geneuer erläutert wird.

herzlichen Dank im Voraus!!

Kommentiert: warum die Aussage, ein NP-schweres Problem lässt sich auf ein NP-schweres Problem reduzieren, falsch?

Sat, 10 Oct 2015 10:42:25 +0000

Nachdem mir heute im Tut die Frage gestellt wurde, noch ein kleiner zusätzlicher Tipp:

-Es ist NICHT danach gefragt, welche Spalte aus der jeweiligen Zeile folgt, sondern für welche Spalten die Zeile gilt!!!

Bsp aus Zeile 1:

[A poly. reduzierbar auf SAT] gilt für [A NP-vollst.] und [A aus NP] .

Falsch ist die Interpretation:

Aus [A poly. reduzierbar auf SAT] folgt [A ist NP-vollst.]

(wie im Tut erwähnt muss, dass nicht sein, denn A kann ja auch ein ganz 'einfaches' Probelm sein ;) )

Liebe Grüße

Bastian (Tutor)

Beantwortet: Kann mir jemand erklären warum bei A-NP-schwer das dritte Feld nicht angekreuzt ist

Sat, 10 Oct 2015 10:38:12 +0000

zunächst: deine Definition von NP-Schwer ist unvollständig. Wenn für alle L in NP [tex]L <=_{pol}[/tex] L' gilt, dann ist L' NP-Schwer. Ein einzelnes L aus NP reicht nicht aus.

Diese Definition gilt nur in eine "Richtung". Es gibt keinen Satz , der besagt, dass wenn L' NP-schwer ist, dann für alle L mit [tex]L<=_{pol}[/tex] L' gilt, dass L in NP liegt und dies ist auch nicht Inhalt obiger Definition.

Tobias (Tutor)