Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

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

+1 Punkt
26 Aufrufe

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

Gefragt 10, Okt 2015 in 2009-H-04 von updkn updkn Info-Genie (6,630 Punkte)  

Eine Antwort

0 Punkte

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)

Beantwortet 10, Okt 2015 von updkn updkn Info-Genie (6,630 Punkte)  
...