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

Kategorien

0 Pluspunkte 1 Minuspunkt
135 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?
...