Würde gerne wissen, ob meine Erklärungen für die einzelnen Aussagen stimmen

Question

1) A ist NP-schwer, da NP-schwer mindestens so schwer wie alle Probleme in NP ist, aber auch semientscheidbar bzw. auch nicht entscheidabr sein kann.

2) vgl. 1) bloß mit B statt A

3) Wegen Inklusion, NP-v. ist auf NP-s. in Polynomialzeit reduzierbar, deshalb auch NP-v.?

4) NP-v. würde heißen, dass das Problem auch NP-schwer ist, als auch, dass es in NP liegt, aber B lässt sich laut Aufgabe nicht weiter reduzieren, kann also auh nicht in NP liegen und damit auch nicht NP-v. sein?

5) A lässt sich in Polynomialzeit auf SAT reduzieren, da A NP-s ist und NP-v. bedeutet, dass das Problem sowohl NP-schwer ist, als auch in NP liegt?

6) Bezieht sich auf das was Tobias oben geschrieben hat, dass wenn gilt P = NP es für NP-vollständige Probleme einen deterministischen Algorithmus mit polynomieller Laufzeit gibt und deshalb lässt sich dann auch B in Poly.zeit auf PRIMES reduzieren, da B NP-schwer ist?!

7) Richtig, da nicht gesagt wurde, dass P != NP, sonst wäre diese Aussage falsch, oder? dann C nicht aus NP kommen würde und es lassen sich doch nur Probleme reduzieren, die aus NP kommen, oder?

8) wurde schon oben erklärt

9) Ja, da A NP-vollständig ist, und das die Eigenschaft es die Eigenschaft von NP-v. ist in nichtdet- Poly.zeit lösbar zu sein.

10) Falsch, da dies schon oben an der Definition "Primes <=pol SAT" ablesbar ist. Und sich NP-v. Probleme nicht auf P reduzieren lassen, das würde mir umgekehrt gelten mit der Annahme P=NP.

 

Und noch eine allgemeine Frage, in der Aufgabe steht ja, dass A NP-v. ist und SAT auch NP-v. ist und weiterhin "SAT <=pol A" aber wie kann sich ein NP-v. Problem auf ein NP-v. Problem reduzieren lassen? Die liegen doch schon in der gleichen Problemklasse?!

 

 

Answer 1

1) A ist NP-schwer, da NP-schwer mindestens so schwer wie alle Probleme in NP ist, aber auch semientscheidbar bzw. auch nicht entscheidabr sein kann.

2) vgl. 1) bloß mit B statt A

3) Wegen Inklusion, NP-v. ist auf NP-s. in Polynomialzeit reduzierbar, deshalb auch NP-v.?

4) NP-v. würde heißen, dass das Problem auch NP-schwer ist, als auch, dass es in NP liegt, aber B lässt sich laut Aufgabe nicht weiter reduzieren, kann also auh nicht in NP liegen und damit auch nicht NP-v. sein?

5) A lässt sich in Polynomialzeit auf SAT reduzieren, da A NP-s ist und NP-v. bedeutet, dass das Problem sowohl NP-schwer ist, als auch in NP liegt?

6) Bezieht sich auf das was Tobias oben geschrieben hat, dass wenn gilt P = NP es für NP-vollständige Probleme einen deterministischen Algorithmus mit polynomieller Laufzeit gibt und deshalb lässt sich dann auch B in Poly.zeit auf PRIMES reduzieren, da B NP-schwer ist?!

7) Richtig, da nicht gesagt wurde, dass P != NP, sonst wäre diese Aussage falsch, oder? dann C nicht aus NP kommen würde und es lassen sich doch nur Probleme reduzieren, die aus NP kommen, oder?

8) wurde schon oben erklärt

9) Ja, da A NP-vollständig ist, und das die Eigenschaft es die Eigenschaft von NP-v. ist in nichtdet- Poly.zeit lösbar zu sein.

10) Falsch, da dies schon oben an der Definition "Primes <=pol SAT" ablesbar ist. Und sich NP-v. Probleme nicht auf P reduzieren lassen, das würde mir umgekehrt gelten mit der Annahme P=NP.

 

Und noch eine allgemeine Frage, in der Aufgabe steht ja, dass A NP-v. ist und SAT auch NP-v. ist und weiterhin "SAT <=pol A" aber wie kann sich ein NP-v. Problem auf ein NP-v. Problem reduzieren lassen? Die liegen doch schon in der gleichen Problemklasse?!

 

 

Comments

Ist deine Aussage: "B mindestens NP-vollständig" -> korrekt
nicht ein Widerspruch zur Lösung der 4. Frage, die besagt das B eben nicht NP-nollständig ist?

---

Mit der obigen Aussage ist sicherlich gemeint, dass B mindestens so schwer ist wie ein NP-vollständiges Problem, das heißt aber nicht automatisch, dass B auch in NP liegen muss.

---

Nein, ich sehe da keinen Widerspruch.

Mit "B mindestens NP-vollständig" ist gemeint, dass B NP-vollständig sein KANN, aber nicht in NP liegen muss (und damit auch NICHT NP-Vollständig sein MUSS), weil B beispielsweise semientscheidbar ist. Das einzige, dass wir aus den gegebenen Informationen sicher wissen, ist, dass B NP-Schwer ist (siehe Frage 2).

Allgemein sollte ich vielleicht noch anmerken, dass nicht jedes semientscheidbare Problem NP-schwer ist.

Die Lösung der 4. Frage ("falsch") bedeutet nur, dass wir auf Basis der Informationen in der Aufgabe nicht beweisen können, dass B NP-vollständig ist.  Das ist etwas anderes als zu zeigen, dass B nicht NP-vollständig sein kann (was man mit den Informationen aus der Aufgabe nicht kann). Insbesondere bedeutet die Lösung von Aufgabe 4 nicht, dass B nicht NP-vollständig ist. Zur Bedeutung der Antwort "falsch" in dieser Aufgabe siehe mein erster Beitrag.

Tobias (Tutor)

Answer 2

zu Anonym von 14.21 Uhr:

1) unvollständig. Nicht jedes Problem A, dass schwieriger ist als alle Probleme in NP ist NP-schwer. Es muss zusätzlich noch JEDES Problem in NP in polynomieller Zeit auf X reduzieren lassen. Dies kann man damit begründen, dass man ein beliebiges Problem aus NP zuerst Polynomiell auf SAT und dann von SAT auf A in Polynomzeit reduzieren kann. Insofern hat 22.59 Uhr recht.

2) korrekt.

3) siehe 22.59 Uhr

4) NP-v. würde heißen, dass das Problem auch NP-schwer ist, als auch, dass es in NP liegt. Aus der Aufgabe kann jedoch man keine Aussage treffen, ob B in NP liegt oder nicht. --> Aussage nicht beweisbar --> "falsch" ankreuzen (s.o.)

5)  siehe 22.59 Uhr

6) du argumentierst in die falsche Richtung. Die Frage ist, ob aus B >=pol Primes P = NP folgt, nicht, ob aus P = NP B>=pol Primes folgt. ansonsten siehe 22.59 Uhr

7) 22.59 Uhr hat recht, unabhängig von ?P = NP? liegt jedes Problem in P auch in NP.

9) korrekt.

10) kann nur gelten, wenn P=NP. P=NP ist meiner Meinung nach aber nur eine NOTWENDIGE aber keine HINREICHENDE Bedingung.

@22.59 Uhr: hoffe, du kannst selber aus meinen Antworten auf 14.21 Uhr ablesen, welche deiner Antworten korrekt sind.

@13.17 Uhr: Nur weil man "falsch" ankreuzt, muss die Aussage nicht falsch sein (siehe meine obere Antwort). Sie kann mit den gegebenen Informationen nur nicht bewiesen werden. Es ist also durchaus möglich, dass B NP-Vollständig ist.

Tobias (Tutor)