Question

Kann mir jemand erklären warum bei A-NP-schwer das dritte Feld nicht angekreuzt ist, weil es heißt doch per definition, dass L' NP-schwer ist wenn L <=(pol) L'  mit L Element NP.

In diese Beispiel müsste demnach doch B, wie in der Aussage angegeben in NP liegen, wenn es auf A (welches NP-schwer ist) reduziert werden kann...

 

danke

Answer 1

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)