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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 1 Minuspunkt
91 Aufrufe

Hallo,

ich würde gerne wissen, ob meine gefundenen Begründungen für die Aussagen stimmen.

1) Ist falsch, weil NP-schwere Probleme auch mehr als Poly.zeit in Anspruch nehmen können und NP-Probleme (also auch NP-vollständige Probleme) sind auf NP-schwere Probleme reduzierbar und nicht umgekehrt, wie es in der Aussage steht.

2) Ist falsch, da A in NP-vollständig liegen KANN, aber nicht muss, da ja nicht ganz NP auch NP-vollständig ist.

3) Hiert verstehe ich nicht wieso die Aussage falsch ist.

Da B laut Aufgabe in nichtdeterminitischer Polynomialzeit lösbar ist und warum sollte es dann nicht auf C reduzierbar sein? Oder würde sich B hier nur auf NP-vollständig reduzieren lassen, da NP-vollständig die schwersten Probleme sind?

4) Ist wahr, da SAT NP-vollständig ist und damit das schwerste Problem. Also lassen sich alle Probleme auf SAT reduzieren?

5) Steht schon eine Begründung in der Lösung, aber die besagt doch im Prinzip das Gleiche wie ich in 2), oder?

6) Ist wahr, da es zwar unendlich viele ganzzahlige Primzahlen gibt, es aber nur einen Algorithmus braucht, um dies zu überprüfen und das Problem damit entscheidbar ist?

7) Ist wahr, aber die Umkehrung würde hier nicht gelten, oder? Also "Jede aufzählbare Menge ist auch entscheidbar". Da nicht jede abzählbare Menge auch entscheidabr ist, da es nur abzählbar viele Algorithmem gibt aber überabzählbar viele abzählbare Mengen, sodass es nicht zu jeder abzählbaren Menge ein Entscheidungsverfahren geben kann.

Oder gibt es einen Unterschied zwischen abzählbar und aufzählbar?

 

in BER-AI von utdbu utdbu Tutor(in) (107k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

1) fast richtig, allerdings liegen alle NP-schweren Probleme (nach heutigem Wissensstand, sowie der Annahme in der Aufgabe) außerhalb von P und sind somit deterministisch eben nicht polynomiell berechenbar, sondern nur nichtdeterministisch. Besser wäre es zu sagen, dass NP-Schwere Probleme auch außerhalb von NP liegen können (sich ihre Komplexität von NP-vollständigen Problemen also um mehr als einen polynomiellen Faktor unterscheiden kann)

2) Stimmt

3) Annahme war hier P != NP. C liegt aber in P. Würde sich B (als NP-vollständiges Problem - beachte auch die zweite Eigenschaft von B) auf C polynomialzeit reduzieren lassen, dann wäre C ebenfalls NP-vollständig, es würde also gelten P = NP, was ein Widerspruch zur Annahme ist.

4) Nein, es ist nicht das schwerste Problem, lediglich gehört es zu den "schwersten Problemen in NP", also den NP-vollständigen. Es lassen sich nur Probleme in NP auf NP-vollständige Probleme reduzieren, was aber für B zutrifft.

5) Wir betrachten sonst immer den Fall, dass P != NP ist. Gilt aber P = NP, dann gilt i.A. auch, dass P = NP = NP-vollständig. Aber es gibt eben noch diese zwei Spezialfälle die nicht in NP-vollständig liegen, aber in P=NP.

6) Das hat nichts mit der Zahl der Algorithmen zu tun, sondern mit der Möglichkeit eines Algorithmus, in endlicher Zeit zu entscheiden, ob die Zahl eine Primzahl ist oder nicht. Der einfachste Algorithmus ist der, der alle Zahlen von 2 bis Wurzel(n) durchläuft und eine Division testet. Da n gegeben ist, sind das endlich viele Schritte. Kann n durch keinen der Werte geteilt werden, so ist es eine Primzahl. Kann es durch einen oder mehrere geteilt werden, so ist es keine. Also kann eine Entscheidung (in beide Richtungen) in endlicher Zeit stattfinden

7) Es gilt: Entscheidbare Mengen < aufzählbare Mengen < abzählbare Mengen (< steht dabei für echt Teilmenge). Daraus kann man sich dann die Implikationen herleiten

Ich hoffe, ich konnte dir weiterhelfen.

Viele Grüße

Philippe

 

von utdbu utdbu Tutor(in) (107k Punkte)  
Wieso ist B NP-vollständig?
...