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.)

Aufgabe 5

+3 Punkte
68 Aufrufe
Ich verstehe die Aufgabe nicht. wieso liegt F in NP und ist nicht NP vollständig? Wieso können wir über F eine spezifischere Aussage als über D machen? Wieso liegt C sicher in P?
Gefragt 2, Feb 2016 in 2012-H-05 von updjl updjl Lernwillige(r) (340 Punkte)  
Kategorie geändert 2, Feb 2016 von Lukas König

2 Antworten

+1 Punkt
Weil Clique NP-vollständig ist und Clique in Pol-Zeit auf F reduziert werden kann, ist F NP-schwer. Denn alle Probleme in NP-vollständig haben die Eigenschaft, dass alle Probleme aus NP auf sie reduzierbar sind - und da die Polynomialzeitreduktion eine transitive Relation ist, ist auch jedes Problem aus NP auf F reduzierbar. Über D können wir diese Aussage nicht treffen, weil PRIMES nicht NP-vollständig ist. Allerdings steht nirgends, dass F NICHT in NP ist, das ist nur aus den gegebenen Aussagen nicht ableitbar - aber auch nicht widerlegbar. Ebenso könnte auch D NP-schwer sein oder in NP oder sogar P liegen - wir können das nur nicht aus den Aussagen ableiten.

C ist in Pol-Zeit reduzierbar auf PRIMES, ist also "höchstens so schwer wie" PRIMES. Da PRIMES in P ist, ist auch C in P.
Beantwortet 2, Feb 2016 von Lukas König Dozent (10,065,100 Punkte)  
Warum liegen A und B in NP vollständig?
+2 Punkte
Unsere einzige Information über F ist hier, dass CLIQUE polynomialzeitreduzierbar auf F ist. Da CLIQUE NP-vollständig ist, also unter anderem NP-schwer ist, können wir folgern, dass F ebenfalls NP-schwer ist also dass jedes Problem aus NP polynomialzeitreduzierbar auf F ist. Dies ist möglich, da wir wissen, dass bereits jedes Problem aus NP auf CLIQUE polynomialzeitreduzierbar ist. Über die Zugehörigkeit von F zu der Menge NP (bzw. einer anderen Menge) haben wir jedoch keine Information. Deshalb liegt es nur in NP-schwer.

Von D wissen wir nur, dass PRIMES polynomialzeitreduzierbar auf D ist. Das grenzt jedoch nicht weiter ein, in welcher Klasse das Problem liegt, weshalb es ganz außen eingeordnet ist.

C liegt in P, da es auf PRIMES polynomialzeitreduzierbar ist. Ensprechend muss es "mindestens so leicht wie PRIMES sein". Folglich wird es in die Klasse P eingeordnet

Grüße,
Lukas (Tutor)
Beantwortet 2, Feb 2016 von uwdll uwdll Tutor(in) (102,360 Punkte)  
...