Aufgabe 5

Question

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?

Answer 1

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)

Answer 2

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.